Submission #53433

#	Time	Username	Problem	Language	Result	Execution time	Memory
53433		fallingstar	The Big Prize (IOI17_prize)	C++14	100 / 100	50 ms	5536 KiB

prize

#include <cassert>
#include <iostream>
#include <vector>

using namespace std;

const int N = 2e5 + 2;

vector<int> cache[N];
vector<int> lv(1, 1);

int sumUpper = 0;

vector<int> ask(int i);
int countQuery = 0;
vector<int> Ask(int i)
{
    assert(++countQuery <= 6000);
    return ask(i);
}

inline bool Type(int i) { return cache[i][0] + cache[i][1] == sumUpper; }

int Solve(int l, int r, int cntL, int cntR)
{
    int cur = sumUpper - cntL - cntR;
    
    if (l > r || cur == 0) return -1;
    
    int i = (l + r) / 2;
    while (true)
    {
        if (cache[i].empty()) cache[i] = Ask(i);
        if (cache[i][0] + cache[i][1] == 0) return i;
        if (Type(i)) 
            return max(Solve(l, i - 1, cntL, cache[i][1]), Solve(i + 1, r, cache[i][0], cntR));
        if (i == r) return Solve(l, (l + r) / 2 - 1, cntL, cntR + r - (l + r) / 2 + 1);
        ++i;
    }
    return -1;
}

int find_best(int n)
{
    for (int i = 1, sum = 1; ; ++i)
    {
        int nex = lv.back() * lv.back() + 1;
        if (sum + nex + (long long) nex * nex + 1 <= n)
        {
            lv.push_back(nex);
            sum += nex * nex;
        }
        else
        {
            int &cur = lv.back();
            while (sum + 1 + (cur + 1) * (cur + 1) + 1 <= n) ++cur;
            break;
        }
    }
    
    
    int upp = 1;
    for (int i = 0; i < (int) lv.size(); ++i)
        upp += lv[i];
    
    for (int i = 0; i < n; ++i)
        if ((i + 1) % (n / upp) == 0) 
        {
            cache[i] = Ask(i);
            sumUpper = max(sumUpper, cache[i][0] + cache[i][1]);
        }
    
    int last = -1, sumL = 0;
    for (int i = 0, need = 0; i < n; ++i)
    {
        if (!cache[i].empty() && cache[i][0] + cache[i][1] == 0) return i;
        need += (i + 1) % (n / upp) == 0;
        need -= !cache[i].empty() && Type(i);
        if (need && cache[i].empty())
        {
            cache[i] = Ask(i);
            --need;
        }
        if (!cache[i].empty() && Type(i))
        {
            int solved = Solve(last + 1, i - 1, sumL, cache[i][1]);
            if (solved != -1) return solved;
            last = i;
            sumL = cache[i][0];
        }
    }
    return Solve(last + 1, n - 1, sumL, 0);
}

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