Submission #1065431

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065431		mc061	The Big Prize (IOI17_prize)	C++17	90 / 100	57 ms	2760 KiB

prize

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

const int N = 2e5+6;
bool is_worst[N]={};
bool know[N]={};
pair<int, int> val[N];

int C = 0;

unordered_map<int, set<int, greater<int>>> last_by_sum;

vector<int> ask(int i);

pair<int, int> get(int i) {
    if (know[i]) {
        return val[i];
    }
    ++C;
    assert(C <= 10000);
    know[i] = true;
    auto now = ask(i);
    val[i].first = now[0], val[i].second = now[1];
    last_by_sum[now[0] + now[1]].insert(i);
    return {now[0], now[1]};
}

int find_best(int n) {
    int mx = 0;
    for (int i = 0; i < min(n, 550); ++i) {
        auto now = get(i);
        val[i].first = now.first;
        val[i].second = now.second;
        mx = max(mx, val[i].first + val[i].second);
        last_by_sum[val[i].first + val[i].second].insert(i);
        if (val[i].first + val[i].second == 0) return i; 
    }
    for (int i = 0; i < min(n, 550); ++i) {
        if (val[i].first + val[i].second == mx) {
            is_worst[i] = true;
            know[i] = true;
        }
        if (val[i].first + val[i].second == 0) return i;
    }
    int l = 550;
    while (true) {
        auto now = get(l);
        if (now.first + now.second == 0) return l;
        
        if (now.first + now.second == mx) break;
        ++l;
    }
    while (true) {
        int low = l+1, high = n-1;
        int pl = l;
        while (high != low) {
            int mid = (high + low + 1) >> 1;
            auto now = get(mid);
            int sum = now.first + now.second;
            if (sum == mx) {
                if (now.first == val[l].first) {
                    low = mid+1;
                }
                else {
                    high = mid-1;
                }
                continue;
            }
            if (now.first + now.second == 0) return mid;
            int v = mid;
            bool worth_left = true;
            while (sum < mx && worth_left) {
                --v;
                now = get(v);
                sum = now.first + now.second;
                if (sum == mx) break;
                set<int, greater<int>>& s = last_by_sum[sum];
                auto it = s.upper_bound(v);
                if (it != s.end()) {
                    if (val[v].first == val[*it].first) {
                        worth_left = false;
                        break;
                    }
                }
                if (sum == 0) return v;
            }
            if (!worth_left) {
                int v = mid;
                get(v);
                sum = val[v].first + val[v].second;
                while (sum < mx) {
                    ++v;
                    now = get(v);
                    sum = now.first + now.second;
                    if (sum == 0) return v;
                }
                l = v;
                break;
            }
            if (now.first == val[l].first) {
                int v = mid;
                sum = val[v].first + val[v].second;
                while (sum < mx) {
                    ++v;
                    now = get(v);
                    sum = now.first + now.second;
                    if (sum == 0) return v;
                }
                l = v;
                break;
            }
            high = v-1;
        }
        if (pl == l) {
            auto x = get(low);
            if (x.first + x.second == 0) return low;
            l = low+1;
            get(l);
            int sum = val[l].first + val[l].second;
            if (sum == 0) return l;
            while (sum < mx) {
                ++l;
                get(l);
                sum = val[l].first + val[l].second;
                if (sum == 0) return l;
            }
        }
    }
}

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