Submission #898224

#	Time	Username	Problem	Language	Result	Execution time	Memory
898224		PersistentLife	Gardening (RMI21_gardening)	C++14	100 / 100	16 ms	1160 KiB

Main

/*
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 / 5
• Subtask 2: 6 / 6
• Subtask 3: 10 / 10
• Subtask 4: 18 / 18
• Subtask 5: 39 / 39
• Subtask 6: 22 / 22