Submission #798231

#	Time	Username	Problem	Language	Result	Execution time	Memory
798231		PixelCat	The Big Prize (IOI17_prize)	C++14	20 / 100	2 ms	3452 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_64 rng(48763);

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(vector<int> v) {
    if(sz(v) == 1) return v[0];
    int len = sz(v);
    // int tot = 0;
    // For(_, 1, 5) {
    //     pii p = qry(v[rng() % len]);
    //     tot = max(tot, p.F + p.S);
    // }
    int tot = 1;
    vector<int> res;
    For(i, 0, tot - 1) {
        int lo, hi = len;
        if(!sz(res)) lo = -1;
        else lo = res.back();
        while(hi - lo > 1) {
            int mi = (hi + lo) / 2;
            pii p = qry(v[mi]);
            if(p.F + p.S < tot || p.F > i) hi = mi;
            else lo = mi;
        }
        assert(hi < len);
        res.eb(hi);
    }
    return solve(res);
}

i32 find_best(i32 n) {
    fill(mem, mem + MAXN + 10, pii(-1, -1));
    vector<int> v(n);
    For(i, 0, n - 1) v[i] = i;
    return solve(v);
}

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