Submission #1061306

#	Time	Username	Problem	Language	Result	Execution time	Memory
1061306		Zicrus	The Big Prize (IOI17_prize)	C++17	20 / 100	965 ms	1048576 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;
    vector<vector<ll>> degBoxes(n);
    set<ll> degs;
    for (int i = n-1; i >= n - 2*root && i >= 0; i--) {
        ll deg = get(i).first + get(i).second;
        degBoxes[deg].push_back(i);
        mxDeg = max(mxDeg, deg);
        degs.insert(deg);
    }
    int m = max(n - 2*root, 0);
    if (!degBoxes[0].empty()) {
        return degBoxes[0][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;
            while (deg < mxDeg) {
                degBoxes[deg].push_back(mid);
                mid--;
                val = get(mid);
                deg = val.first + val.second;
                cnt++;
            }
            if (cnt > 0) {
                int ptr = 0;
                while (cnt--) vst[val.first + ptr++] = true;
            }
            if (vst[i]) break;
            
            if (val.first <= i) {
                left = mid;
            }
            else {
                right = mid-1;
            }
        }
        if (vst[i]) continue;

        degBoxes[get(left).first + get(left).second].push_back(left);
        vst[i] = true;
    }

    return degBoxes[0][0];
}

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