Submission #742336

#	Time	Username	Problem	Language	Result	Execution time	Memory
742336		jamezzz	Gardening (RMI21_gardening)	C++17	100 / 100	103 ms	16868 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define sf scanf
#define pf printf
typedef bitset<50000> bs;

int k,n,m,cnt;
vector<vector<int>> grid;
map<int,bs> memo[500];

bs dp(int n,int m){
	if(n==0&&m==0)return bs(1);
	if(n<=0||m<=0)return bs(0);
	if(memo[n].find(m)!=memo[n].end()){
		return memo[n][m];
	}
	memo[n][m]=(dp(n,m-2)<<(n/2))|(dp(n-2,m-2)<<1)|(dp(n-2,m)<<(m/2));
	return memo[n][m];
}

void square(int x,int y,int h,int w){
	//pf("square %d %d %d %d\n",x,y,h,w);
	int c=cnt++;
	for(int i=0;i<w;++i){
		grid[x][y+i]=grid[x+h-1][y+i]=c;
	}
	for(int i=0;i<h;++i){
		grid[x+i][y]=grid[x+i][y+w-1]=c;
	}
}

void backtrack(int n,int m,int k,int x,int y){
	if(n==0&&m==0)return;
	if(n<=0||m<=0)return;
	
	//pf("backtrack %d %d %d %d %d\n",n,m,k,x,y);
	
	if((dp(n,m-2)<<(n/2))[k]){
		for(int i=0;i<n;i+=2){
			//2x2 square at x+i,y
			square(x+i,y,2,2);
		}
		backtrack(n,m-2,k-n/2,x,y+2);
	}
	else if((dp(n-2,m)<<(m/2))[k]){
		for(int i=0;i<m;i+=2){
			//2x2 square at x,y+i
			square(x,y+i,2,2);
		}
		backtrack(n-2,m,k-m/2,x+2,y);
	}
	else{
		//nxm square at x,y
		square(x,y,n,m);
		backtrack(n-2,m-2,k-1,x+1,y+1);
	}
}

void solve(){
	sf("%d%d%d",&n,&m,&k);
	if(n%2||m%2||k>(n/2)*(m/2)){
		pf("NO\n");
		return;
	}
	int on=n,om=m;
	if(n>m)swap(n,m);
	if(dp(n,m)[k]){
		pf("YES\n");
		grid.resize(n);
		for(int i=0;i<n;++i)grid[i].resize(m);
		cnt=1;
		backtrack(n,m,k,0,0);
		if(on==n){
			for(int i=0;i<n;++i){
				for(int j=0;j<m;++j)pf("%d ",grid[i][j]);
				pf("\n");
			}
		}
		else{
			for(int j=0;j<m;++j){
				for(int i=0;i<n;++i)pf("%d ",grid[i][j]);
				pf("\n");
			}
		}
	}
	else pf("NO\n");
}

int main(){
	int tc;sf("%d",&tc);
	while(tc--)solve();
}

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:66:11: warning: unused variable 'om' [-Wunused-variable]
   66 |  int on=n,om=m;
      |           ^~
Main.cpp:61:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |  sf("%d%d%d",&n,&m,&k);
      |    ^
Main.cpp: In function 'int main()':
Main.cpp:91:11: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |  int tc;sf("%d",&tc);
      |           ^

• Subtask 1: 5 / 5
• Subtask 2: 6 / 6
• Subtask 3: 10 / 10
• Subtask 4: 18 / 18
• Subtask 5: 39 / 39
• Subtask 6: 22 / 22