Submission #798263

#	Time	Username	Problem	Language	Result	Execution time	Memory
798263		PixelCat	The Big Prize (IOI17_prize)	C++14	20 / 100	71 ms	1896 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;
    For(i, 0, tot - 1) {
        int lo, hi = n;
        if(!sz(res)) lo = -1;
        else lo = res.back();
        while(hi - lo > 1) {
            int mi = (hi + lo) / 2;
            pii p = qry(mi);
            if(p.F + p.S > tot) return -88;
            if(p.F + p.S < tot || p.F > i) hi = mi;
            else lo = mi;
        }
        assert(hi < n);
        res.eb(hi);
    }

    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: 0 / 80