Submission #1155350

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155350		onbert	The Big Prize (IOI17_prize)	C++17	90 / 100	26 ms	5388 KiB

prize

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

vector<int> ask(int i);

const int maxn = 2e5 + 5;
vector<int> ans[maxn];
int cnt = 0;
vector<int> qry(int i) {
    if (ans[i].size() == 2) return ans[i];
    else {
        cnt++;
        // assert(cnt <= 10000);
        return ans[i] = ask(i);
    }
}

int find_best(int n) {
    int mx = 0;
    for (int i=0;i<500;i++) {
        int val = qry(i)[0] + qry(i)[1];
        if (val == 0) return i;
        mx = max(val, mx);
    }
    assert(cnt == 500);
	for (int i=500;i<n;i++) {
        vector<int> vec = qry(i);
        if (vec[0] + vec[1] == 0) return i;
        if (vec[0] + vec[1] == mx) {
            int l = i, r = n-1;
            if (qry(i+1) == vec && i+2 < n && qry(i+2) == vec) {
                while (l < r) {
                    int mid = (l+r+1)/2;
                    if (qry(mid) == vec) l = mid;   
                    else r = mid-1;
                }
            }
            i = l;
        }
    }
	return 0;
}

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