Submission #237899

#	Time	Username	Problem	Language	Result	Execution time	Memory
237899		lyc	The Big Prize (IOI17_prize)	C++14	99.68 / 100	73 ms	1016 KiB

prize

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

#define TRACE(x) cout << #x << " :: " << x << endl;
#define _ << " " <<

const int mxN = 2e5+5;
const int mxQ = 10000;
int n, q = 0;
map<int,vector<int>> cache;

vector<int> query(int i) {
    //TRACE("QUERY" _ i);
    assert(i >= 0 && i < n);
    if (cache.count(i)) return cache[i];
    assert(++q <= mxQ);
    return cache[i] = ask(i);
}

int find_best(int _n) {
    n = _n;
    int mxc = 0;
    for (int i = 0; i < min(n,473); ++i) {
        auto res = query(i);
        mxc = max(mxc,res[0]+res[1]);
    }
    int b = 255;
    for (int i = b; i < n; i += 255) {
        query(i);
    }
    int pre = 0;
    for (int i = 0; i < n;) {
        auto res = query(i);
        int c = res[0]+res[1];
        if (c == 0) return i;
        pre += (c == mxc);
        auto it = cache.upper_bound(i);
        while (it != cache.end()) {
            auto y = it->second;
            if (y[0]+y[1] == mxc && y[0] == i+1-pre) ++it;
            else break;
        }
        int lo = prev(it)->first, hi = (it == cache.end() ? n : it->first);
        while (hi-lo > 1) {
            int mid = (lo+hi)/2;
            auto y = query(mid);
            if (y[0]+y[1] == mxc && y[0] == i+1-pre) lo = mid;
            else hi = mid;
        }
        pre += hi-i-1;
        i = hi;
    }
    assert(false);
	return 0;
}

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