Submission #1080566

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080566		TB_	The Big Prize (IOI17_prize)	C++17	90 / 100	88 ms	39416 KiB

prize

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define fo(i, n) for(ll i = 0; i<(n); i++)
#define F first
#define S second
#define pb push_back
#define deb(x) cout << #x << " = " << (x) << endl
#define deb2(x, y) cout << #x << " = " << (x) << ", " << #y << " = " << (y) << endl

typedef vector<ll> vl;
typedef vector<vl> vvl;

int find_best(int n);
std::vector<int> ask(int i);
// std::vector<int> ask(int i){
//     ll gaah = 2;
//     if(i==gaah) return {0, 0};
//     else if(i>gaah) return {1, 0};
//     else return {0, 1};
//     // if(i==0) return {0, 3};
//     // if(i==1) return {0, 0};
//     // if(i==2) return {1, 0};
//     // if(i==3) return {2, 1};
//     // if(i==4) return {2, 1};
//     // if(i==5) return {1, 0};
//     // else return {3, 0};
// }

ll valval = 1;

struct Node{
    Node *lnode, *rnode;
    ll l, r, val = valval;
    Node(ll l, ll r) : l(l), r(r){
        if(r-l>1){
            ll mid = (r+l) / 2;
            lnode = new Node(l, mid);
            rnode = new Node(mid, r);
            val = lnode->val+rnode->val;
        }
    }

    void update(ll lo, ll hi){
        if(r <= lo || hi <= l) return;
        if(r <= hi && lo <= l){
            val = 0;
            return;
        }
        lnode->update(lo, hi);rnode->update(lo, hi); 
        val = lnode->val+rnode->val;
    }
    void update2(ll lo, ll hi){
        if(r <= lo || hi <= l) return;
        if(r <= hi && lo <= l){
            val = 1;
            return;
        }
        lnode->update2(lo, hi);rnode->update2(lo, hi); 
        val = lnode->val+rnode->val;
    }

    ll sumQuery(ll lo, ll hi){
        if(r <= lo || hi <= l) return 0;
        if(r <= hi && lo <= l) return val;
        return lnode->sumQuery(lo, hi)+rnode->sumQuery(lo, hi); 
    }

    ll query(ll x){
        if(r-l == 1){
            // val = 0;
            return l;
        }
        ll res;
        if(lnode->val>x) res = lnode->query(x);
        else{
            x-=lnode->val;
            res = rnode->query(x);
        }
        val = lnode->val+rnode->val;
        return res;
    }
};

int find_best(int n){
    ll co = 0;
    ll prething = -1;
    mt19937 rng(42);
    fo(i, 500){
        ll temp = rng()%n;
        co++;
        vector<int> res = ask(temp);
        // if(res[0] ==0 && res[1] == 0){
        //     return temp;
        // }
        prething = max(prething, (ll)res[0]+res[1]);
    } 
    Node st(0, n);
    valval = 0;
    Node st2(0, n);
    map<ll, vector<int>> memo;
    while(1){
        // deb("gahh");
        ll lo = 0;
        ll hi = n;
        while(1){
            ll a = st.sumQuery(0, lo);
            ll b = st.sumQuery(0, hi);
            ll pos = st.query((a+b)/2);
            co++;
            vector<int> res;
            // deb(pos);
            // deb2(lo, hi);
            if(memo.count(pos)){
                res = memo[pos];
            }else{
                res = ask(pos);
                memo[pos] = res; 
            }
            // deb(pos);
            if(res[0] ==0 && res[1] == 0){
                return pos;
            }
            if(res[0]+res[1] <prething){
                st.update(pos, pos+1);
                st2.update2(pos, pos+1);
                break;
            }
            res[0]-=st2.sumQuery(0, pos);
            // deb2(res[0], res[1]);
            if(res[0]) hi = pos;
            else lo = pos+1;
        }
    }
}

• Subtask 1: 20 / 20
• Subtask 2: 70 / 80