Submission #1062657

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062657		Zicrus	The Big Prize (IOI17_prize)	C++17	98.31 / 100	32 ms	1960 KiB

prize

#include <bits/stdc++.h>
#include "prize.h"
using namespace std;

typedef long long ll;

vector<pair<int, int>> cache;

pair<int, int> get(int i) {
    if (cache[i].first >= 0) return cache[i];
    auto res = ask(i);
    return cache[i] = {res[0], res[1]};
}

int getSegment(int low, int high, int mxDeg, int idLow, int idHigh) {
    int prevLeft = low;
    vector<bool> vst(idHigh);
    for (int i = idLow; i < idHigh; i++) {
        if (vst[i]) continue;
        int left = prevLeft, right = high-1;
        while (left < right) {
            int mid = (left+right+1)/2;
            pair<int, int> val = get(mid);
            int deg = val.first + val.second;
            int cnt = 0;
            int orig = mid;
            while (deg < mxDeg && mid > 0) {
                if (deg == 0) return mid;
                mid--; right--;
                val = get(mid);
                deg = val.first + val.second;
                cnt++;
            }
            if (deg == 0) return mid;
            if (cnt > 0) {
                int ptr = 0;
                while (cnt--) vst[val.first + ptr++] = true;
            }
            if (vst[i]) {
                prevLeft = orig+1;
                break;
            }
            
            if (val.first <= i) {
                left = mid;
                prevLeft = left+1;
            }
            else {
                right = mid-1;
            }
        }
        if (vst[i]) continue;

        if(get(left).first + get(left).second == 0) return left;
        vst[i] = true;
    }
    return -1;
}

int find_best(int n) {
    cache = vector<pair<int, int>>(n, {-1, -1});
	int root = (int)sqrt(n);
    
    ll mxDeg = 0;
    for (int i = n-1; i >= n - 500 && i >= 0; i--) {
        ll deg = get(i).first + get(i).second;
        if (deg == 0) return i;
        mxDeg = max(mxDeg, deg);
    }
    int m = max(n - 500, 0);

    for (int low = 0; low < m; low += root) {
        pair<int, int> valLow = get(low);
        while (low < m && valLow.first + valLow.second < mxDeg) {
            if (valLow.first + valLow.second == 0) return low;
            valLow = get(++low);
        }
        if (low >= m) break;

        int high = min(low + root, m);
        pair<int, int> valHigh = get(high);
        while (high > low && valHigh.first + valHigh.second < mxDeg) {
            if (valHigh.first + valHigh.second == 0) return high;
            valHigh = get(--high);
        }
        if (high <= low) continue;

        ll ans = getSegment(low, high, mxDeg, valLow.first, valHigh.first);
        if (ans != -1) return ans;
    }

    return 0;
}

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