Submission #246018

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

prize

#include "prize.h"

using namespace std;

#define vi vector<int>

int biggestCt = 0;

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;
        if (sum != biggestCt) continue;
        int ans = solve(mid+1, r, res[0], numRight);
        if (ans != -1) return ans;
        return solve(l, (l+r)/2-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;
        if (sum != biggestCt) continue;
        int ans = solve(l, mid-1, numLeft, res[1]);
        if (ans != -1) return ans;
        break;
    }
	return -1;
}

int find_best(int n) {
    for (int i = 0; i < min(n, 480); i++) {
        vi res = ask(i);
        if (res[0] + res[1] == 0) return i;
        biggestCt = max(biggestCt, res[0] + res[1]);
    }
    return solve(0, n-1, 0, 0);
}

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