This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define sf scanf
#define pf printf
typedef bitset<20> 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%2||m%2||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%2||m%2||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);
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:60:11: warning: unused variable 'om' [-Wunused-variable]
60 | 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:85:11: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
85 | int tc;sf("%d",&tc);
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |