Submission #1061334

#	Time	Username	Problem	Language	Result	Execution time	Memory
1061334		Zicrus	The Big Prize (IOI17_prize)	C++17	90 / 100	59 ms	2132 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 find_best(int n) {
    cache = vector<pair<int, int>>(n, {-1, -1});
	int root = (int)ceil(sqrt(n));
    
    ll mxDeg = 0;
    for (int i = n-1; i >= n - 2*root && i >= 0; i--) {
        ll deg = get(i).first + get(i).second;
        if (deg == 0) return i;
        mxDeg = max(mxDeg, deg);
    }
    int m = max(n - 2*root, 0);

    int prevLeft = 0;
    vector<bool> vst(mxDeg);
    for (int i = 0; i < mxDeg; i++) {
        if (vst[i]) continue;
        int left = prevLeft, right = m-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 0;
}

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