oj.uz

Submission #742334

# Submission time Handle Problem Language Result Execution time Memory
742334 2023-05-16T06:23:44 Z jamezzz Gardening (RMI21_gardening) C++17
0 / 100
 73 ms 8752 KB 
#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(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){
	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((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-n/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

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Failed 73 ms 960 KB Incorrect output
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Failed 73 ms 960 KB Incorrect output
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Failed 73 ms 960 KB Incorrect output
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 8752 KB Execution killed with signal 7
2 Halted 0 ms 0 KB -

Subtask #5
0 / 39.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 6228 KB Execution killed with signal 7
2 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Failed 73 ms 960 KB Incorrect output
2 Halted 0 ms 0 KB -