oj.uz

Submission #898220

# Submission time Handle Problem Language Result Execution time Memory
898220 2024-01-04T11:43:09 Z PersistentLife Gardening (RMI21_gardening) C++14
39 / 100
 15 ms 856 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)
		{
			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);
			
		}
		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 15 ms 856 KB Correct! Azusa and Laika like the garden :)

Subtask #2
6.0 / 6.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 600 KB Correct! Azusa and Laika like the garden :)
2 Correct 6 ms 604 KB Correct! Azusa and Laika like the garden :)
3 Correct 7 ms 600 KB Correct! Azusa and Laika like the garden :)
4 Correct 7 ms 600 KB Correct! Azusa and Laika like the garden :)
5 Correct 7 ms 600 KB Correct! Azusa and Laika like the garden :)
6 Correct 6 ms 604 KB Correct! Azusa and Laika like the garden :)
7 Correct 7 ms 604 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 604 KB Correct! Azusa and Laika like the garden :)
10 Correct 7 ms 604 KB Correct! Azusa and Laika like the garden :)
11 Correct 7 ms 600 KB Correct! Azusa and Laika like the garden :)
12 Correct 6 ms 604 KB Correct! Azusa and Laika like the garden :)
13 Correct 6 ms 600 KB Correct! Azusa and Laika like the garden :)

Subtask #5
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 604 KB Correct! Azusa and Laika like the garden :)
2 Failed 3 ms 604 KB Incorrect output
3 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 856 KB Correct! Azusa and Laika like the garden :)
2 Correct 8 ms 600 KB Correct! Azusa and Laika like the garden :)
3 Correct 8 ms 604 KB Correct! Azusa and Laika like the garden :)
4 Correct 9 ms 604 KB Correct! Azusa and Laika like the garden :)
5 Correct 8 ms 600 KB Correct! Azusa and Laika like the garden :)
6 Correct 7 ms 600 KB Correct! Azusa and Laika like the garden :)
7 Correct 6 ms 604 KB Correct! Azusa and Laika like the garden :)
8 Correct 7 ms 600 KB Correct! Azusa and Laika like the garden :)
9 Correct 7 ms 600 KB Correct! Azusa and Laika like the garden :)
10 Correct 7 ms 600 KB Correct! Azusa and Laika like the garden :)
11 Correct 6 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 :)
14 Correct 7 ms 604 KB Correct! Azusa and Laika like the garden :)
15 Correct 7 ms 604 KB Correct! Azusa and Laika like the garden :)
16 Correct 7 ms 600 KB Correct! Azusa and Laika like the garden :)
17 Correct 6 ms 604 KB Correct! Azusa and Laika like the garden :)
18 Correct 6 ms 600 KB Correct! Azusa and Laika like the garden :)
19 Correct 3 ms 604 KB Correct! Azusa and Laika like the garden :)
20 Failed 3 ms 604 KB Incorrect output
21 Halted 0 ms 0 KB -