Submission #798272

#	Time	Username	Problem	Language	Result	Execution time	Memory
798272		PixelCat	The Big Prize (IOI17_prize)	C++14	100 / 100	45 ms	1904 KiB

prize

#include "prize.h"

#ifdef NYAOWO
#include "grader.cpp"
#endif

#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
// #define int LL
using namespace std;
using i32 = int32_t;
using LL = long long;
using pii = pair<int, int>;

const int MAXN = 200'000;
mt19937 rng(time(NULL));

pii mem[MAXN + 10];
pii qry(int idx) {
    if(mem[idx].F != -1) return mem[idx];
    auto res = ask(idx);
    return mem[idx] = pii(res[0], res[1]);
}

int solve(int n) {
    int tot = 0;
    For(_, 1, 100) {
        pii p = qry((int)(rng() % (LL)n));
        tot = max(tot, p.F + p.S);
    }
    
    vector<int> res;
    bool fail = true;
    while(fail) {
        fail = false;
        res.clear();
        priority_queue<pii, vector<pii>, greater<pii>> pq;
        For(i, 0, tot - 1) {
            int lo, hi = n;
            if(!sz(res)) lo = -1;
            else lo = res.back();
            while(sz(pq) && pq.top().F < i) pq.pop();
            while(sz(pq) && pq.top().F == i) {
                lo = max(lo, pq.top().S);
                pq.pop();
            }
            if(sz(pq)) {
                assert(pq.top().F > i);
                hi = pq.top().S;
            }
            while(hi - lo > 1) {
                int mi = (hi + lo) / 2;
                pii p = qry(mi);
                if(p.F + p.S > tot) {
                    fail = true;
                    tot = p.F + p.S;
                    goto FAIL;
                }
                if(p.F + p.S < tot || p.F > i) hi = mi;
                else lo = mi;
                if(p.F + p.S == tot) pq.emplace(p.F, mi);
            }
            assert(hi < n);
            res.eb(hi);
        }
        FAIL:;
    }

    for(auto &i:res) {
        pii p = qry(i);
        if(p.F + p.S == 0) {
            return i;
        }
    }
    return -8;
}

i32 find_best(i32 n) {
    fill(mem, mem + MAXN + 10, pii(-1, -1));

#ifndef NYAOWO
    if(n <= 5000) {
        For(i, 0, n - 1) {
            pii p = qry(i);
            if(p.F + p.S == 0) return i;
        }
        return -8;
    }
#endif

    return solve(n);
}

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