oj.uz

Submission #742331

# Submission time Handle Problem Language Result Execution time Memory
742331 2023-05-16T06:19:06 Z jamezzz Gardening (RMI21_gardening) C++17
11 / 100
 96 ms 6228 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(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){
	//printf("backtrack %d %d %d %d %d\n",n,m,k,x,y);
	if(n==0&&m==0)return;
	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){
			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:64:11: warning: unused variable 'om' [-Wunused-variable]
   64 |  int on=n,om=m;
      |           ^~
Main.cpp:59:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |  sf("%d%d%d",&n,&m,&k);
      |    ^
Main.cpp: In function 'int main()':
Main.cpp:89:11: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |  int tc;sf("%d",&tc);
      |           ^

Subtask #1
5.0 / 5.0

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

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 972 KB Correct! Azusa and Laika like the garden :)
2 Correct 46 ms 2076 KB Correct! Azusa and Laika like the garden :)
3 Correct 47 ms 1452 KB Correct! Azusa and Laika like the garden :)

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 972 KB Correct! Azusa and Laika like the garden :)
2 Correct 46 ms 2076 KB Correct! Azusa and Laika like the garden :)
3 Correct 47 ms 1452 KB Correct! Azusa and Laika like the garden :)
4 Failed 41 ms 2176 KB Output does not contain all values between 1 and k
5 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Failed 25 ms 6228 KB Output does not contain all values between 1 and k
2 Halted 0 ms 0 KB -

Subtask #5
0 / 39.0

# Verdict Execution time Memory Grader output
1 Failed 12 ms 5188 KB Output does not contain all values between 1 and k
2 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 972 KB Correct! Azusa and Laika like the garden :)
2 Correct 46 ms 2076 KB Correct! Azusa and Laika like the garden :)
3 Correct 47 ms 1452 KB Correct! Azusa and Laika like the garden :)
4 Failed 41 ms 2176 KB Output does not contain all values between 1 and k
5 Halted 0 ms 0 KB -