Submission #1205685

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

treasure

#include <bits/stdc++.h>
using namespace std;
 
#include "treasure.h"
#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 ask(int x,int y){
    return countTreasure(1,1,x+1,y+1);
}
int get_block(int x1,int y1,int x2,int y2){
    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!=0);
        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,n,m,szp)
    dbg(a,b,c,d)
        // F0R(i,4){
        //     F0R(j,4){
        //         cout<<grid[i][j]<<" ";
        //     }
        //     cout<<nl;
        // }
    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)if(ans[i][j])Report(i+1,j+1);
    }
}
 

• Subtask 1: 72 / 100