QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#242740 | #2808. Gardening | starrylasky | 5 | 76ms | 8380kb | C++14 | 2.6kb | 2023-11-07 16:44:37 | 2023-11-07 16:44:37 |
Judging History
answer
///yl/hs/bx/yl
#include<bits/stdc++.h>
#define fep(i,l,r) for(int i=l;i<=r;++i)
#define feb(i,r,l) for(int i=r;i>=l;--i)
#define For(i,u) for(int i=head[u];i;i=e[i].nxt)
#define LL long long
//#define int long long
#define ld long double
#define pi pair<int,int>
#define mpr make_pair
using namespace std;
const int N = 2e5+5,M = 1e7+7,mod = 998244353;
inline int read() {
int s=0,w=1; char ch=getchar();
while(!(ch>='0'&&ch<='9')) {if(ch=='-') w=-1; ch=getchar();}
while( ch>='0'&&ch<='9') {s=(s<<1)+(s<<3)+ch-'0'; ch=getchar();}
return s*w;
}
inline int Mod(int x) {return x>=mod?x-mod:x;}
inline void addmod(int &x,int y) {x=Mod(x+y);}
inline void chkmax(auto &x,auto y) {x=max(x,y);}
inline void chkmin(auto &x,auto y) {x=min(x,y);}
namespace starrylasky {
int now; vector<int > a[N];
inline void Solve(int k,int lx,int rx,int ly,int ry) {
if(lx>rx) return ;
cerr<<k<<" "<<lx<<" "<<rx<<" "<<ly<<" "<<ry<<" "<<4*(k-2)+2*(rx-lx+1+ry-ly+1)<<" "<<(rx-lx+1)*(ry-ly+1)<<"\n";
if((rx-lx+1)*(ry-ly+1)==4*k) {
for(int nx=lx;nx<rx;nx+=2) for(int ny=ly;ny<ry;ny+=2) {
++now; fep(k,0,1) fep(p,0,1) a[nx+k][ny+p]=now;
}
return ;
}
else if(4*(k-2)+2*(rx-lx+1+ry-ly+1)>=(rx-lx+1)*(ry-ly+1)) fep(i,3,rx-lx+1) {
int x=i,y=((rx-lx+1)*(ry-ly+1)-4*(k-2))/2-x;
// cerr<<x<<" "<<rx-lx<<" "<<y<<" "<<ry-ly<<"\n";
if(x<=rx-lx+1&&y<=ry-ly+1&&!(x&1)&&!(y&1)) {
++now; //cerr<<lx<<" "<<lx+x-1<<"\n";
fep(j,ly,ly+y-1) a[lx][j]=a[lx+x-1][j]=now;
fep(j,lx,lx+x-1) a[j][ly]=a[j][ly+y-1]=now;
for(int nx=lx+1;nx<lx+x-1;nx+=2) for(int ny=ly+1;ny<ly+y-1;ny+=2) {
++now; fep(k,0,1) fep(p,0,1) a[nx+k][ny+p]=now;
}
for(int nx=lx+x;nx<rx;nx+=2) for(int ny=ly;ny<ry;ny+=2) {
++now; fep(k,0,1) fep(p,0,1) a[nx+k][ny+p]=now;
}
for(int nx=lx;nx<rx;nx+=2) for(int ny=ly+y;ny<ry;ny+=2) {
++now; fep(k,0,1) fep(p,0,1) a[nx+k][ny+p]=now;
}
return ;
}
}
++now;
fep(i,lx,rx) a[i][ly]=a[i][ry]=now;
fep(i,ly,ry) a[lx][i]=a[rx][i]=now;
Solve(k-1,lx+1,rx-1,ly+1,ry-1);
}
inline void Main() {
int n=read(),m=read(),k=read(); now=0;
if((n&1)||(m&1)) return cout<<"NO\n",void();
if(k>n*m/4||k==n*m/4-1||k<max(n,m)/2||k==max(n,m)/2+1) return cout<<"NO\n",void();
fep(i,1,n) a[i].resize(m+5);
Solve(k,1,n,1,m); cout<<"YES\n"; cerr<<now<<" "<<k<<"\n";
fep(i,1,n) fep(j,1,m) cout<<a[i][j]<<" \n"[j==m];
fep(i,1,n) vector<int > ().swap(a[i]);
}
}
signed main() {
ios::sync_with_stdio(false);
int _T=read();
while(_T--) starrylasky::Main();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 5
Accepted
Test #1:
score: 5
Accepted
time: 76ms
memory: 8256kb
input:
28119 2 4 2 2 2 1 4 2 2 2 2 1 2 2 1 2 2 3 2 4 2 4 4 2 2 2 2 2 2 2 4 4 3 2 2 1 4 2 2 4 4 4 4 2 2 2 4 2 2 2 2 2 2 2 2 2 1 2 2 1 2 2 1 2 2 1 2 2 2 2 2 1 2 4 2 2 2 1 2 2 1 2 2 1 4 2 2 2 2 2 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 4 2 7 2 2 1 2 4 2 2 2 1 4 2 2 2 4 2 2 2 1 2 4 4 2 2 1 2 2 1 2 2 1 4 2 2 2 2 2 2 2 1 ...
output:
YES 1 1 2 2 1 1 2 2 YES 1 1 1 1 YES 1 1 1 1 2 2 2 2 YES 1 1 1 1 YES 1 1 1 1 NO YES 1 1 2 2 1 1 2 2 YES 1 1 1 1 1 2 2 1 1 2 2 1 1 1 1 1 NO NO NO YES 1 1 1 1 YES 1 1 1 1 2 2 2 2 YES 1 1 2 2 1 1 2 2 3 3 4 4 3 3 4 4 YES 1 1 1 1 2 2 2 2 YES 1 1 2 2 1 1 2 2 NO NO YES 1 1 1 1 YES 1 1 1 1 YES 1 1 1 1 YES 1 ...
result:
ok Correct! Azusa and Laika like the garden :) (28119 test cases)
Subtask #2:
score: 0
Wrong Answer
Dependency #1:
100%
Accepted
Test #2:
score: 0
Wrong Answer
time: 4ms
memory: 8380kb
input:
2953 2 2 1 2 12 6 2 34 17 2 26 51 2 2 1 2 2 1 2 24 12 4 4 2 4 50 45 2 28 14 4 4 4 4 48 48 2 22 11 2 26 13 4 2 2 4 2 2 2 22 11 2 38 19 2 40 20 2 38 19 2 40 20 4 30 23 2 16 8 4 4 3 2 44 2 4 42 85 2 2 1 2 32 53 2 2 1 4 18 60 2 6 9 2 10 5 2 50 25 4 26 77 2 2 4 2 40 20 4 4 4 2 2 1 2 2 1 2 36 2 2 18 9 4 4...
output:
YES 1 1 1 1 YES 1 1 2 2 3 3 4 4 5 5 6 6 1 1 2 2 3 3 4 4 5 5 6 6 YES 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 NO YES 1 1 1 1 YES 1 1 1 1 YES 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9...
result:
wrong answer Incorrect output (test case 43)
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Wrong Answer
Test #6:
score: 0
Wrong Answer
time: 3ms
memory: 8268kb
input:
311 2 2 1 12 12 14 6 6 6 40 40 297 28 28 82 30 30 74 4 4 10 38 38 210 6 6 4 42 42 365 8 8 11 16 16 30 6 6 7 22 22 38 10 10 5 2 2 2 12 12 19 16 16 52 28 28 124 26 26 92 2 2 2 28 28 25 20 20 19 18 18 43 4 4 3 30 30 78 26 26 130 18 18 58 26 26 59 6 6 4 10 10 6 14 14 34 18 18 184 12 12 108 18 18 35 30 3...
output:
YES 1 1 1 1 YES 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 1 1 2 3 3 3 3 3 3 3 3 2 1 1 2 3 4 4 5 5 6 6 3 2 1 1 2 3 4 4 5 5 6 6 3 2 1 1 2 3 3 3 3 3 3 3 3 2 1 1 2 7 7 8 8 9 9 10 10 2 1 1 2 7 7 8 8 9 9 10 10 2 1 1 2 11 11 12 12 13 13 14 14 2 1 1 2 11 11 12 12 13 13 14 14 2 1 1 2 2 2 2 2 2 2 2 2 2 1 ...
result:
wrong answer Output contains values not between 1 and k (test case 5)
Subtask #5:
score: 0
Wrong Answer
Test #19:
score: 0
Wrong Answer
time: 3ms
memory: 8344kb
input:
310 44 2 22 36 8 195 2 2 4 2 50 61 12 42 275 4 4 5 26 30 416 24 20 252 20 32 498 30 30 130 32 48 1153 46 16 574 4 40 89 6 28 64 10 16 9 18 42 152 4 14 1 6 50 280 10 10 87 44 24 395 2 2 4 40 46 273 34 34 607 22 22 300 40 40 1166 10 48 211 42 22 334 6 10 20 38 38 189 6 10 36 14 14 33 44 48 1518 32 18 ...
output:
YES 1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4 5 5 5 5 6 6 6 6 7 7 7 7 8 8 8 8 9 9 9 9 10 10 10 10 11 11 11 11 12 12 12 12 13 13 13 13 14 14 14 14 15 15 15 15 16 16 16 16 17 17 17 17 18 18 18 18 19 19 19 19 20 20 20 20 21 21 21 21 22 22 22 22 NO NO NO NO NO NO NO NO YES 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
result:
wrong answer Incorrect output (test case 15)
Subtask #6:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%