Submission #68201795

Source Code Expand

#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
typedef long long int ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<vvl> vvvl;
typedef vector<vvvl> vvvvl;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<vvb> vvvb;
typedef vector<vvvb> vvvvb;
typedef pair<ll,ll> pl;
typedef pair<ll,pl> ppl;
typedef pair<ll,ppl> pppl;
typedef pair<ll,pppl> pppppl;
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(a) begin(a),end(a)
#define sz(a) (int)(a).size()
#define F first
#define S second
#define bs(A,x) binary_search(all(A),x)
#define lb(A,x) (ll)(lower_bound(all(A),x)-A.begin())
#define ub(A,x) (ll)(upper_bound(all(A),x)-A.begin())
#define cou(A,x) (ll)(upper_bound(all(A),x)-lower_bound(all(A),x))
template<typename T>using min_priority_queue=priority_queue<T,vector<T>,greater<T>>;
template<class T>bool chmax(T&a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T>bool chmin(T&a,T b){if(b<a){a=b;return 1;}return 0;}
//*
using mint=modint998244353;
const ll mod=998244353;
//*/
/*
using mint=modint1000000007;
const ll mod=1000000007;
//*/
//using mint=modint;
//*
typedef vector<mint> vm;
typedef vector<vm> vvm;
typedef vector<vvm> vvvm;
typedef vector<vvvm> vvvvm;
ostream&operator<<(ostream&os,mint a){os<<a.val();return os;}
istream&operator>>(istream&is,mint&a){int x;is>>x;a=mint(x);return is;}
//*/
template<typename T1,typename T2>ostream&operator<<(ostream&os,pair<T1,T2>p){os<<p.F<<" "<<p.S;return os;}
template<typename T1,typename T2>istream&operator>>(istream&is,pair<T1,T2>&p){is>>p.F>>p.S;return is;}
template<typename T>ostream&operator<<(ostream&os,vector<T>v){rep(i,0,sz(v))os<<v[i]<<(i+1!=sz(v)?" ":"");return os;}
template<typename T>istream&operator>>(istream&is,vector<T>&v){for(T&in:v)is>>in;return is;}
int main(){
  cin.tie(0)->sync_with_stdio(0);
  cin.exceptions(cin.failbit);
  ll T;cin>>T;
  while(T--){
    ll H,W,L,N,M,x,y;cin>>H>>W>>L>>N>>M>>x>>y;x--;y--;
    vl A(L),B(L);
    rep(i,0,H)A[i%L]+=W;
    rep(j,0,W)B[j%L]+=H;
    A[x%L]--;
    B[y%L]--;
    if(*min_element(all(A))<M||*min_element(all(B))<N){cout<<"No"<<endl;continue;}
    bool ok=1;
    rep(i,0,L)if((A[i]-M)%L)ok=0;
    rep(j,0,L)if((B[j]-N)%L)ok=0;
    if(!ok){cout<<"No"<<endl;continue;}
    assert(H%L==W%L);
    if(x%L==0){
      assert(H%L==1&&W%L==1&&x%L==0&&y%L==0);
      ll h=H/L,w=W/L;
      vector<pl>X,Y;
      rep(i,0,y/L)X.emplace_back(pl(x,L*i));
      rep(i,y/L,w)X.emplace_back(pl(x,L*i+1));
      rep(i,0,x/L)Y.emplace_back(pl(L*i,y));
      rep(i,x/L,h)Y.emplace_back(pl(L*i+1,y));
      rep(i,0,h)rep(j,0,w){
        ll p=i*L,q=j*L;
        if(p>=x)p++;
        if(q>=y)q++;
        if(sz(X)<N){
          rep(k,0,L)X.emplace_back(pl(p+k,q));
        }
        else{
          rep(k,0,L)Y.emplace_back(pl(p,q+k));
        }
      }
      if(sz(X)!=N||sz(Y)!=M){
        cout<<"No"<<endl;
        continue;
      }
      cout<<"Yes"<<endl;
      for(auto[x,y]:X)cout<<x+1<<" "<<y+1<<endl;
      for(auto[x,y]:Y)cout<<x+1<<" "<<y+1<<endl;
      assert(sz(X)==N&&sz(Y)==M);
    }
    else{
      assert(H%L==L-1&&W%L==L-1&&x%L==L-1&&y%L==L-1);
      ll h=(H+1)/L,w=(W+1)/L;
      vector<pl>X,Y;
      rep(i,0,L-1){
        X.emplace_back(pl(x-L+1+i,y-L+1));
        X.emplace_back(pl(x+1+i,y));
        Y.emplace_back(pl(x,y-L+1+i));
        Y.emplace_back(pl(x-L+1,y+1+i));
      }
      rep(i,0,y/L)rep(j,0,L-1)X.emplace_back(pl(x-L+1+j,L*i));
      rep(i,y/L+2,w)rep(j,0,L-1)X.emplace_back(pl(x-L+1+j,L*i-1));
      rep(i,0,x/L)rep(j,0,L-1)Y.emplace_back(pl(L*i,y-L+1+j));
      rep(i,x/L+2,h)rep(j,0,L-1)Y.emplace_back(pl(L*i-1,y-L+1+j));
      rep(i,0,x/L)rep(j,0,y/L){
        ll p=i*L,q=j*L;
        if(sz(X)<N){
          rep(k,0,L)X.emplace_back(pl(p+k,q));
        }
        else{
          rep(k,0,L)Y.emplace_back(pl(p,q+k));
        }
      }
      rep(i,0,x/L)rep(j,y/L+1,w){
        ll p=i*L,q=j*L-1;
        if(sz(X)<N){
          rep(k,0,L)X.emplace_back(pl(p+k,q));
        }
        else{
          rep(k,0,L)Y.emplace_back(pl(p,q+k));
        }
      }
      rep(i,x/L+1,h)rep(j,0,y/L){
        ll p=i*L-1,q=j*L;
        if(sz(X)<N){
          rep(k,0,L)X.emplace_back(pl(p+k,q));
        }
        else{
          rep(k,0,L)Y.emplace_back(pl(p,q+k));
        }
      }
      rep(i,x/L+1,h)rep(j,y/L+1,w)if(i!=x/L+1||j!=y/L+1){
        ll p=i*L-1,q=j*L-1;
        if(sz(X)<N){
          rep(k,0,L)X.emplace_back(pl(p+k,q));
        }
        else{
          rep(k,0,L)Y.emplace_back(pl(p,q+k));
        }
      }
      if(sz(X)!=N||sz(Y)!=M){
        cout<<"No"<<endl;
        continue;
      }
      cout<<"Yes"<<endl;
      for(auto[x,y]:X)cout<<x+1<<" "<<y+1<<endl;
      for(auto[x,y]:Y)cout<<x+1<<" "<<y+1<<endl;
      assert(sz(X)==N&&sz(Y)==M);
    }
  }
  return 0;
}

Submission Info

Submission Time
Task E - Tile Grid with One Hole
User TKTYI
Language C++ 20 (gcc 12.2)
Score 800
Code Size 5057 Byte
Status AC
Exec Time 524 ms
Memory 12748 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 800 / 800
Status
AC × 1
AC × 80
Set Name Test Cases
Sample sample.txt
All 1.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 2.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 3.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 4.txt, 40.txt, 41.txt, 42.txt, 43.txt, 44.txt, 45.txt, 46.txt, 47.txt, 48.txt, 49.txt, 5.txt, 50.txt, 51.txt, 52.txt, 53.txt, 54.txt, 55.txt, 56.txt, 57.txt, 58.txt, 59.txt, 6.txt, 60.txt, 61.txt, 62.txt, 63.txt, 64.txt, 65.txt, 66.txt, 67.txt, 68.txt, 69.txt, 7.txt, 70.txt, 71.txt, 72.txt, 73.txt, 74.txt, 75.txt, 76.txt, 77.txt, 78.txt, 79.txt, 8.txt, 9.txt, sample.txt
Case Name Status Exec Time Memory
1.txt AC 216 ms 9620 KiB
10.txt AC 1 ms 3548 KiB
11.txt AC 195 ms 6284 KiB
12.txt AC 5 ms 3664 KiB
13.txt AC 69 ms 4664 KiB
14.txt AC 524 ms 12748 KiB
15.txt AC 20 ms 3700 KiB
16.txt AC 1 ms 3540 KiB
17.txt AC 208 ms 7664 KiB
18.txt AC 3 ms 3560 KiB
19.txt AC 220 ms 6044 KiB
2.txt AC 222 ms 6324 KiB
20.txt AC 1 ms 3544 KiB
21.txt AC 129 ms 5296 KiB
22.txt AC 17 ms 3676 KiB
23.txt AC 74 ms 4588 KiB
24.txt AC 1 ms 3420 KiB
25.txt AC 12 ms 3616 KiB
26.txt AC 6 ms 3664 KiB
27.txt AC 3 ms 3504 KiB
28.txt AC 4 ms 3564 KiB
29.txt AC 114 ms 5256 KiB
3.txt AC 1 ms 3456 KiB
30.txt AC 22 ms 3688 KiB
31.txt AC 30 ms 4012 KiB
32.txt AC 6 ms 3596 KiB
33.txt AC 9 ms 3672 KiB
34.txt AC 19 ms 3732 KiB
35.txt AC 68 ms 4516 KiB
36.txt AC 50 ms 3968 KiB
37.txt AC 1 ms 3660 KiB
38.txt AC 5 ms 3636 KiB
39.txt AC 6 ms 3784 KiB
4.txt AC 36 ms 3852 KiB
40.txt AC 9 ms 3564 KiB
41.txt AC 1 ms 3548 KiB
42.txt AC 3 ms 3580 KiB
43.txt AC 96 ms 4352 KiB
44.txt AC 4 ms 3588 KiB
45.txt AC 80 ms 5312 KiB
46.txt AC 314 ms 11560 KiB
47.txt AC 16 ms 3664 KiB
48.txt AC 259 ms 7580 KiB
49.txt AC 199 ms 7492 KiB
5.txt AC 5 ms 3652 KiB
50.txt AC 1 ms 3672 KiB
51.txt AC 3 ms 3492 KiB
52.txt AC 14 ms 3560 KiB
53.txt AC 85 ms 5004 KiB
54.txt AC 201 ms 7380 KiB
55.txt AC 4 ms 3636 KiB
56.txt AC 130 ms 5452 KiB
57.txt AC 3 ms 3556 KiB
58.txt AC 21 ms 3900 KiB
59.txt AC 1 ms 3508 KiB
6.txt AC 1 ms 3524 KiB
60.txt AC 19 ms 3648 KiB
61.txt AC 2 ms 3620 KiB
62.txt AC 1 ms 3560 KiB
63.txt AC 105 ms 5692 KiB
64.txt AC 93 ms 4744 KiB
65.txt AC 1 ms 3540 KiB
66.txt AC 5 ms 3624 KiB
67.txt AC 34 ms 3972 KiB
68.txt AC 1 ms 3588 KiB
69.txt AC 4 ms 3716 KiB
7.txt AC 105 ms 5544 KiB
70.txt AC 228 ms 7840 KiB
71.txt AC 56 ms 4436 KiB
72.txt AC 76 ms 5272 KiB
73.txt AC 1 ms 3432 KiB
74.txt AC 11 ms 3676 KiB
75.txt AC 305 ms 8036 KiB
76.txt AC 2 ms 3560 KiB
77.txt AC 2 ms 3492 KiB
78.txt AC 4 ms 3608 KiB
79.txt AC 1 ms 3436 KiB
8.txt AC 5 ms 3656 KiB
9.txt AC 126 ms 5444 KiB
sample.txt AC 1 ms 3428 KiB