| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1205669 | Mighilon | Treasure (different grader from official contest) (CEOI13_treasure2) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include "../Library/debug.h"
#else
#define dbg(x...)
#endif
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define F0R(i, a) for (int i = 0; i < (a); ++i)
#define FORd(i, a, b) for (int i = (b) - 1; i >= (a); --i)
#define F0Rd(i, a) for (int i = (a) - 1; i >= 0; --i)
#define trav(a, x) for (auto& a : x)
#define f first
#define s second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) x.begin(), x.end()
const char nl = '\n';
const int INF = 1e9;
const int MOD = 1e9 + 7;
int grid[100][100];
bool ans[100][100];
int query(int x, int y){
if(min(x,y)<0)
return 0;
return grid[x][y];
}
void setgrid(int x1,int y1,int x2,int y2,int val){
FOR(i,x1,x2+1){
FOR(j,y1,y2+1){
grid[i][j]=val;
ans[i][j]=val!=0;
if(i&&j)grid[i][j]+=grid[i-1][j]+grid[i][j-1]-grid[i-1][j-1];
else if(i)grid[i][j]+=grid[i-1][j];
else if(j)grid[i][j]+=grid[i][j-1];
}
}
}
// int gx[4][4]={
// {1,1,1,0},
// {0,1,0,1},
// {0,0,0,1},
// {1,0,1,0}};
int gx[5][5]={
{1,1,1,0,1},
{0,1,0,1,0},
{0,0,0,1,1},
{1,0,1,0,0},
{0,0,0,1,1}
};
int ask(int x,int y){
#ifdef DEBUG
int res=0;
F0R(i,x+1)F0R(j,y+1)res+=gx[i][j];
return res;
#else
cout<<"1 1 "<<x+1<<" "<<y+1<<endl;
int res;
cin>>res;
return res;
#endif
}
int get_block(int x1,int y1,int x2,int y2){
vector<vi> aux;
FOR(i,x1,x2+1){
vi tmp;
FOR(j,y1,y2+1){
tmp.pb(gx[i][j]);
}
aux.pb(tmp);
}
dbg(x1,y1,x2,y2);
// if(x1==0&&y1==2&&x2==1&&y2==2){
// F0R(i,4){
// F0R(j,4){
// cout<<grid[i][j]<<" ";
// }
// cout<<nl;
// }
// }
dbg(aux)
dbg(ask(x2,y2),query(x1-1,y2),query(x2,y1-1),query(x1-1,y1-1));
dbg(ask(x2,y2)-query(x1-1,y2)-query(x2,y1-1)+query(x1-1,y1-1));
return ask(x2,y2)-query(x1-1,y2)-query(x2,y1-1)+query(x1-1,y1-1);
}
void solve_block(int x, int y,int n,int m,int szp){
if(szp==0||(m==1&&n==1)||szp==n*m){
setgrid(x,y,x+n-1,y+m-1,szp);
return;
}
int a=0,b=0,c=0,d=0;
// m = 1||n = 1
if(n==1){
assert(m==2);
assert(szp==1);
b=szp;
a=get_block(x,y,x+(n+1)/2-1,y+(m+1)/2-1);
b-=a;
solve_block(x,y,(n+1)/2,(m+1)/2,a);
solve_block(x,y+(m+1)/2,(n+1)/2,m/2,b);
return;
}
else if(m==1){
assert(n==2);
assert(szp==1);
c=szp;
a=get_block(x,y,x+(n+1)/2-1,y+(m+1)/2-1);
c-=a;
solve_block(x,y,(n+1)/2,(m+1)/2,a);
solve_block(x+(n+1)/2,y,n/2,(m+1)/2,c);
return;
}
//---
b=get_block(x,y,x+(n+1)/2-1,y+m-1);
if(b){
a=get_block(x,y,x+(n+1)/2-1,y+(m+1)/2-1);
b-=a;
}
d=szp-b-a;
if(d){
c=get_block(x,y,x+n-1,y+(m+1)/2-1)-a;
d-=c;
}
dbg(x,y,m,szp)
dbg(a,b,c,d)
assert(min({a,b,c,d})>=0);
solve_block(x,y,(n+1)/2,(m+1)/2,a);
solve_block(x,y+(m+1)/2,(n+1)/2,m/2,b);
solve_block(x+(n+1)/2,y,n/2,(m+1)/2,c);
solve_block(x+(n+1)/2,y+(m+1)/2,n/2,m/2,d);
}
void solve(){
int n=0;
cin>>n;
solve_block(0,0,n,n,get_block(0,0,n-1,n-1));
cout<<"END"<<nl;
F0R(i,n){
F0R(j,n)cout<<ans[i][j];
cout<<nl;
}
}
int32_t main(){
ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int TC = 1;
// cin >> TC;
while(TC--){
solve();
}
return 0;
}