Submission #937828

#	Time	Username	Problem	Language	Result	Execution time	Memory
937828		Alcabel	The Big Prize (IOI17_prize)	C++17	90 / 100	55 ms	668 KiB

prize

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

const int need = 473;

int find_best(int n) {
    int mxcnt = 0;
    vector<int> res;
    int nonmax = 0;
    for (int i = 0; i < min(n, need); ++i) {
        res = ask(i);
        if (res[0] + res[1] == 0) {
            return i;
        }
        if (res[0] + res[1] > mxcnt) {
            mxcnt = res[0] + res[1];
            nonmax = i;
        } else if (res[0] + res[1] < mxcnt) {
            ++nonmax;
        }
    }
    int last = need - 1;
    while (true) {
        int left = last, right = n;
        while (right - left > 1) {
            int mid = left + (right - left) / 2;
            res = ask(mid);
            if (res[0] + res[1] == 0) {
                return mid;
            }
            if (res[0] + res[1] < mxcnt) {
                right = mid;
            } else if (res[0] == nonmax) {
                left = mid;
            } else {
                right = mid;
            }
        }
        assert(right != n);
        last = right;
        ++nonmax;
    }
}

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