Submission #1205674

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205674		Mighilon	Treasure (different grader from official contest) (CEOI13_treasure2)	C++20	0 / 100	1 ms	584 KiB

treasure

#include <bits/stdc++.h>
using namespace std;
 
#ifdef DEBUG
#include "../Library/debug.h"
#else
#include "treasure.h"
#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 findTreasure(int 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;
    }
}
 
#ifdef DEBUG
int32_t main(){
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    
    int TC = 1;
    // cin >> TC;
    while(TC--){
        // solve();
        findTreasure(5);
    }
    return 0;
}
#endif

• Subtask 1: 0 / 100