Submission #246025

#	Time	Username	Problem	Language	Result	Execution time	Memory
246025		thecodingwizard	The Big Prize (IOI17_prize)	C++11	100 / 100	60 ms	512 KiB

prize

#include "prize.h"

using namespace std;

#define vi vector<int>

int biggestCt = -1;

int solve(int l, int r, int numLeft, int numRight) {
    if (l > r) return -1;

    if (numLeft + numRight == biggestCt) return -1;
    for (int mid = (l+r)/2; mid <= r; mid++) {
        vi res = ask(mid);
        int sum = res[0] + res[1];
        if (sum == 0) return mid;
        bool change = false;
        if (sum > biggestCt) {
            biggestCt = sum;
        }
        if (sum != biggestCt) continue;
        int ans = solve(mid+1, r, res[0], change ? -1 : numRight);
        if (ans != -1) return ans;
        return solve(l, (l+r)/2-1, change ? -1 : numLeft, res[1] + mid-(l+r)/2);
    }
    for (int mid = (l+r)/2-1; mid >= l; mid--) {
        vi res = ask(mid);
        int sum = res[0] + res[1];
        if (sum == 0) return mid;
        bool change = false;
        if (sum > biggestCt) {
            biggestCt = sum;
        }
        if (sum != biggestCt) continue;
        int ans = solve(l, mid-1, change ? -1 : numLeft, res[1]);
        if (ans != -1) return ans;
        break;
    }
	return -1;
}

int find_best(int n) {
    return solve(0, n-1, 0, 0);
}

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