oj.uz

Submission #742336

# Submission time Handle Problem Language Result Execution time Memory
742336 2023-05-16T06:25:46 Z jamezzz Gardening (RMI21_gardening) C++17
100 / 100
 103 ms 16868 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){
	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

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.0 / 5.0

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

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 916 KB Correct! Azusa and Laika like the garden :)
2 Correct 45 ms 2076 KB Correct! Azusa and Laika like the garden :)
3 Correct 46 ms 1276 KB Correct! Azusa and Laika like the garden :)

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 916 KB Correct! Azusa and Laika like the garden :)
2 Correct 45 ms 2076 KB Correct! Azusa and Laika like the garden :)
3 Correct 46 ms 1276 KB Correct! Azusa and Laika like the garden :)
4 Correct 41 ms 2160 KB Correct! Azusa and Laika like the garden :)
5 Correct 43 ms 2080 KB Correct! Azusa and Laika like the garden :)

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 6192 KB Correct! Azusa and Laika like the garden :)
2 Correct 23 ms 6036 KB Correct! Azusa and Laika like the garden :)
3 Correct 23 ms 5268 KB Correct! Azusa and Laika like the garden :)
4 Correct 27 ms 5592 KB Correct! Azusa and Laika like the garden :)
5 Correct 23 ms 5076 KB Correct! Azusa and Laika like the garden :)
6 Correct 24 ms 5468 KB Correct! Azusa and Laika like the garden :)
7 Correct 26 ms 5144 KB Correct! Azusa and Laika like the garden :)
8 Correct 22 ms 5452 KB Correct! Azusa and Laika like the garden :)
9 Correct 24 ms 5928 KB Correct! Azusa and Laika like the garden :)
10 Correct 23 ms 5580 KB Correct! Azusa and Laika like the garden :)
11 Correct 24 ms 5736 KB Correct! Azusa and Laika like the garden :)
12 Correct 22 ms 5460 KB Correct! Azusa and Laika like the garden :)
13 Correct 26 ms 5528 KB Correct! Azusa and Laika like the garden :)

Subtask #5
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 5204 KB Correct! Azusa and Laika like the garden :)
2 Correct 12 ms 5588 KB Correct! Azusa and Laika like the garden :)
3 Correct 12 ms 4992 KB Correct! Azusa and Laika like the garden :)
4 Correct 16 ms 5716 KB Correct! Azusa and Laika like the garden :)
5 Correct 15 ms 5972 KB Correct! Azusa and Laika like the garden :)
6 Correct 11 ms 5588 KB Correct! Azusa and Laika like the garden :)
7 Correct 14 ms 5616 KB Correct! Azusa and Laika like the garden :)
8 Correct 13 ms 5728 KB Correct! Azusa and Laika like the garden :)
9 Correct 14 ms 6340 KB Correct! Azusa and Laika like the garden :)
10 Correct 12 ms 5588 KB Correct! Azusa and Laika like the garden :)
11 Correct 15 ms 14160 KB Correct! Azusa and Laika like the garden :)
12 Correct 14 ms 4948 KB Correct! Azusa and Laika like the garden :)
13 Correct 13 ms 5460 KB Correct! Azusa and Laika like the garden :)
14 Correct 13 ms 5632 KB Correct! Azusa and Laika like the garden :)
15 Correct 12 ms 5576 KB Correct! Azusa and Laika like the garden :)
16 Correct 14 ms 5076 KB Correct! Azusa and Laika like the garden :)
17 Correct 15 ms 9684 KB Correct! Azusa and Laika like the garden :)

Subtask #6
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 916 KB Correct! Azusa and Laika like the garden :)
2 Correct 45 ms 2076 KB Correct! Azusa and Laika like the garden :)
3 Correct 46 ms 1276 KB Correct! Azusa and Laika like the garden :)
4 Correct 41 ms 2160 KB Correct! Azusa and Laika like the garden :)
5 Correct 43 ms 2080 KB Correct! Azusa and Laika like the garden :)
6 Correct 27 ms 6192 KB Correct! Azusa and Laika like the garden :)
7 Correct 23 ms 6036 KB Correct! Azusa and Laika like the garden :)
8 Correct 23 ms 5268 KB Correct! Azusa and Laika like the garden :)
9 Correct 27 ms 5592 KB Correct! Azusa and Laika like the garden :)
10 Correct 23 ms 5076 KB Correct! Azusa and Laika like the garden :)
11 Correct 24 ms 5468 KB Correct! Azusa and Laika like the garden :)
12 Correct 26 ms 5144 KB Correct! Azusa and Laika like the garden :)
13 Correct 22 ms 5452 KB Correct! Azusa and Laika like the garden :)
14 Correct 24 ms 5928 KB Correct! Azusa and Laika like the garden :)
15 Correct 23 ms 5580 KB Correct! Azusa and Laika like the garden :)
16 Correct 24 ms 5736 KB Correct! Azusa and Laika like the garden :)
17 Correct 22 ms 5460 KB Correct! Azusa and Laika like the garden :)
18 Correct 26 ms 5528 KB Correct! Azusa and Laika like the garden :)
19 Correct 12 ms 5204 KB Correct! Azusa and Laika like the garden :)
20 Correct 12 ms 5588 KB Correct! Azusa and Laika like the garden :)
21 Correct 12 ms 4992 KB Correct! Azusa and Laika like the garden :)
22 Correct 16 ms 5716 KB Correct! Azusa and Laika like the garden :)
23 Correct 15 ms 5972 KB Correct! Azusa and Laika like the garden :)
24 Correct 11 ms 5588 KB Correct! Azusa and Laika like the garden :)
25 Correct 14 ms 5616 KB Correct! Azusa and Laika like the garden :)
26 Correct 13 ms 5728 KB Correct! Azusa and Laika like the garden :)
27 Correct 14 ms 6340 KB Correct! Azusa and Laika like the garden :)
28 Correct 12 ms 5588 KB Correct! Azusa and Laika like the garden :)
29 Correct 15 ms 14160 KB Correct! Azusa and Laika like the garden :)
30 Correct 14 ms 4948 KB Correct! Azusa and Laika like the garden :)
31 Correct 13 ms 5460 KB Correct! Azusa and Laika like the garden :)
32 Correct 13 ms 5632 KB Correct! Azusa and Laika like the garden :)
33 Correct 12 ms 5576 KB Correct! Azusa and Laika like the garden :)
34 Correct 14 ms 5076 KB Correct! Azusa and Laika like the garden :)
35 Correct 15 ms 9684 KB Correct! Azusa and Laika like the garden :)
36 Correct 34 ms 13240 KB Correct! Azusa and Laika like the garden :)
37 Correct 36 ms 15888 KB Correct! Azusa and Laika like the garden :)
38 Correct 32 ms 9164 KB Correct! Azusa and Laika like the garden :)
39 Correct 35 ms 10956 KB Correct! Azusa and Laika like the garden :)
40 Correct 32 ms 5996 KB Correct! Azusa and Laika like the garden :)
41 Correct 31 ms 7436 KB Correct! Azusa and Laika like the garden :)
42 Correct 32 ms 6456 KB Correct! Azusa and Laika like the garden :)
43 Correct 31 ms 5708 KB Correct! Azusa and Laika like the garden :)
44 Correct 31 ms 5756 KB Correct! Azusa and Laika like the garden :)
45 Correct 38 ms 16868 KB Correct! Azusa and Laika like the garden :)
46 Correct 34 ms 13880 KB Correct! Azusa and Laika like the garden :)
47 Correct 32 ms 6348 KB Correct! Azusa and Laika like the garden :)
48 Correct 34 ms 6252 KB Correct! Azusa and Laika like the garden :)
49 Correct 32 ms 7968 KB Correct! Azusa and Laika like the garden :)
50 Correct 33 ms 6052 KB Correct! Azusa and Laika like the garden :)
51 Correct 34 ms 12936 KB Correct! Azusa and Laika like the garden :)
52 Correct 30 ms 6104 KB Correct! Azusa and Laika like the garden :)
53 Correct 31 ms 6212 KB Correct! Azusa and Laika like the garden :)
54 Correct 30 ms 6168 KB Correct! Azusa and Laika like the garden :)
55 Correct 30 ms 6080 KB Correct! Azusa and Laika like the garden :)
56 Correct 38 ms 16588 KB Correct! Azusa and Laika like the garden :)
57 Correct 32 ms 6628 KB Correct! Azusa and Laika like the garden :)
58 Correct 37 ms 8780 KB Correct! Azusa and Laika like the garden :)
59 Correct 37 ms 15872 KB Correct! Azusa and Laika like the garden :)
60 Correct 34 ms 8224 KB Correct! Azusa and Laika like the garden :)