QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#242740#2808. Gardeningstarrylasky5 76ms8380kbC++142.6kb2023-11-07 16:44:372023-11-07 16:44:37

Judging History

你现在查看的是最新测评结果

  • [2023-11-07 16:44:37]
  • 评测
  • 测评结果:5
  • 用时:76ms
  • 内存:8380kb
  • [2023-11-07 16:44:37]
  • 提交

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%