Submission #424444

#	Time	Username	Problem	Language	Result	Execution time	Memory
424444		timmyfeng	The Big Prize (IOI17_prize)	C++17	97.67 / 100	64 ms	328 KiB

prize

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

#include "prize.h"

const int K = 474;

int lolli;

vector<int> ask(int i);

int solve(int l, int r, int sum_l, int sum_r) {
    if (l >= r || sum_l == sum_r) {
        return 0;
    }

    int ml = (l + r) / 2, mr = ml;
    while (mr < r) {
        vector<int> value = ask(mr);
        if (value[0] + value[1] == lolli) {
            return solve(l, ml, sum_l, value[0] - (mr - ml)) ^ solve(mr + 1, r, value[0], sum_r);
        } else if (value[0] + value[1] == 0) {
            return mr;
        }
        ++mr;
    }

    return solve(l, ml, sum_l, sum_r - (mr - ml));
}

int find_best(int n) {
    for (int i = 0; i < min(n, K); ++i) {
        vector<int> value = ask(i);
        lolli = max(lolli, value[0] + value[1]);
    }
    return solve(0, n, 0, lolli);
}

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