oj.uz

Submission #898224

# Submission time Handle Problem Language Result Execution time Memory
898224 2024-01-04T11:45:30 Z PersistentLife Gardening (RMI21_gardening) C++14
100 / 100
 16 ms 1160 KB 
/*
Things to notice:
1. do not calculate useless values
2. do not use similar names
 
Things to check:
1. submit the correct file
2. time (it is log^2 or log)
3. memory
4. prove your naive thoughts 
5. long long
6. corner case like n=0,1,inf or n=m
7. check if there is a mistake in the ds or other tools you use
8. fileio in some oi-contest

9. module on time 
10. the number of a same divisor in a math problem
11. multi-information and queries for dp and ds problems
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define pii pair<long long,long long>
#define mp make_pair
#define pb push_back
const int mod=998244353;
const int inf=0x3f3f3f3f;
const int INF=1e18;
int n,m,uidx;
vector <vector<int> > ans;
void fill2()
{
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) 
		if(!ans[i][j]&&!ans[i+1][j]&&!ans[i][j+1]&&!ans[i+1][j+1]) uidx++,ans[i][j]=ans[i+1][j]=ans[i][j+1]=ans[i+1][j+1]=uidx;
}
bool work(int x1,int y1,int x2,int y2,int K)
{
//	cout<<x1<<" "<<y1<<" "<<x2<<" "<<y2<<" "<<(x2-x1+1)*(y2-y1+1)/4<<" "<<K<<"\n";
	if(K<=0) return 0;
	if(x1>x2||y1>y2) return 0;
	if((x2-x1+1)*(y2-y1+1)==4*K) 
	{
		fill2();
		return 1;
	}
	int l1=-1,l2=-1;
	for(int len1=4;len1<=x2-x1+1;len1+=2) for(int len2=4;len2<=y2-y1+1;len2+=2) 
		if((x2-x1+1)*(y2-y1+1)-2*len1-2*len2+4==4*(K-1)) l1=len1,l2=len2;

	if(l1==-1&&l2==-1) 
	{
		if(x1+1==x2||y1+1==y2) return 0;
		l1=x2-x1+1,l2=y2-y1+1;
		if((x2-x1-1)*(y2-y1-1)/4==K)
		{
			if(x2-x1+1<=y2-y1+1)
			{
				for(int i=x1;i<=x2;i+=2) uidx++,K--,ans[i][y1]=ans[i][y1+1]=ans[i+1][y1]=ans[i+1][y1+1]=uidx;
				return work(x1,y1+2,x2,y2,K);
			}
			else
			{
				for(int i=y1;i<=y2;i+=2) uidx++,K--,ans[x1][i]=ans[x1][i+1]=ans[x1+1][i]=ans[x1+1][i+1]=uidx;
				return work(x1+2,y1,x2,y2,K);
			}
		}
		uidx++;
		for(int i=x1;i<=x1+l1-1;i++) ans[i][y1]=ans[i][y1+l2-1]=uidx;
		for(int i=y1;i<=y1+l2-1;i++) ans[x1][i]=ans[x1+l1-1][i]=uidx;
		return work(x1+1,y1+1,x2-1,y2-1,K-1);
	}
	uidx++;
	for(int i=x1;i<=x1+l1-1;i++) ans[i][y1]=ans[i][y1+l2-1]=uidx;
	for(int i=y1;i<=y1+l2-1;i++) ans[x1][i]=ans[x1+l1-1][i]=uidx;
	fill2();
	return 1;
}
int K;
void solve()
{
	cin>>n>>m>>K;
	uidx=0;
	if(n%2||m%2)
	{
		cout<<"NO\n";
		return;
	}
	if(K==n*m/4-1)
	{
		cout<<"NO\n";
		return;
	}
	ans.clear();
	ans.resize(n+1);
	for(int i=0;i<=n;i++) ans[i].resize(m+1);
	if(work(1,1,n,m,K)) 
	{
		cout<<"YES\n";
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++) cout<<ans[i][j]<<" ";
			cout<<"\n";
		}
	}
	else cout<<"NO\n";

}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int _=1;
	cin>>_;
	while(_--) solve();
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 868 KB Correct! Azusa and Laika like the garden :)

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 868 KB Correct! Azusa and Laika like the garden :)
2 Correct 8 ms 604 KB Correct! Azusa and Laika like the garden :)
3 Correct 8 ms 600 KB Correct! Azusa and Laika like the garden :)

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 868 KB Correct! Azusa and Laika like the garden :)
2 Correct 8 ms 604 KB Correct! Azusa and Laika like the garden :)
3 Correct 8 ms 600 KB Correct! Azusa and Laika like the garden :)
4 Correct 8 ms 604 KB Correct! Azusa and Laika like the garden :)
5 Correct 12 ms 856 KB Correct! Azusa and Laika like the garden :)

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 600 KB Correct! Azusa and Laika like the garden :)
2 Correct 8 ms 604 KB Correct! Azusa and Laika like the garden :)
3 Correct 7 ms 744 KB Correct! Azusa and Laika like the garden :)
4 Correct 7 ms 604 KB Correct! Azusa and Laika like the garden :)
5 Correct 7 ms 604 KB Correct! Azusa and Laika like the garden :)
6 Correct 11 ms 600 KB Correct! Azusa and Laika like the garden :)
7 Correct 8 ms 832 KB Correct! Azusa and Laika like the garden :)
8 Correct 7 ms 604 KB Correct! Azusa and Laika like the garden :)
9 Correct 7 ms 752 KB Correct! Azusa and Laika like the garden :)
10 Correct 10 ms 604 KB Correct! Azusa and Laika like the garden :)
11 Correct 7 ms 604 KB Correct! Azusa and Laika like the garden :)
12 Correct 7 ms 604 KB Correct! Azusa and Laika like the garden :)
13 Correct 7 ms 604 KB Correct! Azusa and Laika like the garden :)

Subtask #5
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 600 KB Correct! Azusa and Laika like the garden :)
2 Correct 3 ms 600 KB Correct! Azusa and Laika like the garden :)
3 Correct 3 ms 604 KB Correct! Azusa and Laika like the garden :)
4 Correct 5 ms 604 KB Correct! Azusa and Laika like the garden :)
5 Correct 5 ms 600 KB Correct! Azusa and Laika like the garden :)
6 Correct 4 ms 604 KB Correct! Azusa and Laika like the garden :)
7 Correct 3 ms 456 KB Correct! Azusa and Laika like the garden :)
8 Correct 4 ms 600 KB Correct! Azusa and Laika like the garden :)
9 Correct 4 ms 604 KB Correct! Azusa and Laika like the garden :)
10 Correct 5 ms 600 KB Correct! Azusa and Laika like the garden :)
11 Correct 3 ms 600 KB Correct! Azusa and Laika like the garden :)
12 Correct 3 ms 604 KB Correct! Azusa and Laika like the garden :)
13 Correct 3 ms 604 KB Correct! Azusa and Laika like the garden :)
14 Correct 4 ms 604 KB Correct! Azusa and Laika like the garden :)
15 Correct 3 ms 604 KB Correct! Azusa and Laika like the garden :)
16 Correct 3 ms 604 KB Correct! Azusa and Laika like the garden :)
17 Correct 3 ms 616 KB Correct! Azusa and Laika like the garden :)

Subtask #6
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 868 KB Correct! Azusa and Laika like the garden :)
2 Correct 8 ms 604 KB Correct! Azusa and Laika like the garden :)
3 Correct 8 ms 600 KB Correct! Azusa and Laika like the garden :)
4 Correct 8 ms 604 KB Correct! Azusa and Laika like the garden :)
5 Correct 12 ms 856 KB Correct! Azusa and Laika like the garden :)
6 Correct 8 ms 600 KB Correct! Azusa and Laika like the garden :)
7 Correct 8 ms 604 KB Correct! Azusa and Laika like the garden :)
8 Correct 7 ms 744 KB Correct! Azusa and Laika like the garden :)
9 Correct 7 ms 604 KB Correct! Azusa and Laika like the garden :)
10 Correct 7 ms 604 KB Correct! Azusa and Laika like the garden :)
11 Correct 11 ms 600 KB Correct! Azusa and Laika like the garden :)
12 Correct 8 ms 832 KB Correct! Azusa and Laika like the garden :)
13 Correct 7 ms 604 KB Correct! Azusa and Laika like the garden :)
14 Correct 7 ms 752 KB Correct! Azusa and Laika like the garden :)
15 Correct 10 ms 604 KB Correct! Azusa and Laika like the garden :)
16 Correct 7 ms 604 KB Correct! Azusa and Laika like the garden :)
17 Correct 7 ms 604 KB Correct! Azusa and Laika like the garden :)
18 Correct 7 ms 604 KB Correct! Azusa and Laika like the garden :)
19 Correct 5 ms 600 KB Correct! Azusa and Laika like the garden :)
20 Correct 3 ms 600 KB Correct! Azusa and Laika like the garden :)
21 Correct 3 ms 604 KB Correct! Azusa and Laika like the garden :)
22 Correct 5 ms 604 KB Correct! Azusa and Laika like the garden :)
23 Correct 5 ms 600 KB Correct! Azusa and Laika like the garden :)
24 Correct 4 ms 604 KB Correct! Azusa and Laika like the garden :)
25 Correct 3 ms 456 KB Correct! Azusa and Laika like the garden :)
26 Correct 4 ms 600 KB Correct! Azusa and Laika like the garden :)
27 Correct 4 ms 604 KB Correct! Azusa and Laika like the garden :)
28 Correct 5 ms 600 KB Correct! Azusa and Laika like the garden :)
29 Correct 3 ms 600 KB Correct! Azusa and Laika like the garden :)
30 Correct 3 ms 604 KB Correct! Azusa and Laika like the garden :)
31 Correct 3 ms 604 KB Correct! Azusa and Laika like the garden :)
32 Correct 4 ms 604 KB Correct! Azusa and Laika like the garden :)
33 Correct 3 ms 604 KB Correct! Azusa and Laika like the garden :)
34 Correct 3 ms 604 KB Correct! Azusa and Laika like the garden :)
35 Correct 3 ms 616 KB Correct! Azusa and Laika like the garden :)
36 Correct 12 ms 976 KB Correct! Azusa and Laika like the garden :)
37 Correct 10 ms 860 KB Correct! Azusa and Laika like the garden :)
38 Correct 10 ms 940 KB Correct! Azusa and Laika like the garden :)
39 Correct 15 ms 856 KB Correct! Azusa and Laika like the garden :)
40 Correct 10 ms 736 KB Correct! Azusa and Laika like the garden :)
41 Correct 14 ms 856 KB Correct! Azusa and Laika like the garden :)
42 Correct 10 ms 856 KB Correct! Azusa and Laika like the garden :)
43 Correct 16 ms 860 KB Correct! Azusa and Laika like the garden :)
44 Correct 10 ms 860 KB Correct! Azusa and Laika like the garden :)
45 Correct 10 ms 860 KB Correct! Azusa and Laika like the garden :)
46 Correct 10 ms 860 KB Correct! Azusa and Laika like the garden :)
47 Correct 11 ms 860 KB Correct! Azusa and Laika like the garden :)
48 Correct 12 ms 860 KB Correct! Azusa and Laika like the garden :)
49 Correct 9 ms 1160 KB Correct! Azusa and Laika like the garden :)
50 Correct 11 ms 904 KB Correct! Azusa and Laika like the garden :)
51 Correct 9 ms 856 KB Correct! Azusa and Laika like the garden :)
52 Correct 11 ms 856 KB Correct! Azusa and Laika like the garden :)
53 Correct 11 ms 860 KB Correct! Azusa and Laika like the garden :)
54 Correct 10 ms 856 KB Correct! Azusa and Laika like the garden :)
55 Correct 10 ms 860 KB Correct! Azusa and Laika like the garden :)
56 Correct 10 ms 856 KB Correct! Azusa and Laika like the garden :)
57 Correct 10 ms 856 KB Correct! Azusa and Laika like the garden :)
58 Correct 10 ms 860 KB Correct! Azusa and Laika like the garden :)
59 Correct 12 ms 1116 KB Correct! Azusa and Laika like the garden :)
60 Correct 11 ms 856 KB Correct! Azusa and Laika like the garden :)