Submission #1241681

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241681		SpyrosAliv	The Big Prize (IOI17_prize)	C++20	90 / 100	21 ms	408 KiB

prize

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

int find_best(int n) {
	if (n <= 10000) {
		for (int i = 0; i < n; i++) {
			vector<int> ret = ask(i);
			if (ret[0] + ret[1] == 0) return i;
		}
		assert(false);
		return -1;
	}
	int ll = 0, rr = n-1;
	int need = 0;
	vector<int> lastTot;
	for (int i = 0; i < 500; i++) {
		vector<int> curr = ask(i);
		need = max(need, curr[0] + curr[1]);
		if (curr[0] + curr[1] == 0) return i;
		if (curr[0] + curr[1] == need) {
			ll = i;
			lastTot = curr;
		}
	}
	while (true) {
		int lo = ll+1, hi = rr;
		int idx = -1;
		while (lo <= hi) {
			int mid = (lo + hi) / 2;
			vector<int> tot = ask(mid);
			if (tot[0] + tot[1] == 0) return mid;
			if (tot[0] + tot[1] < need) {
				idx = mid;
				hi = mid-1;
				continue;
			}
			int toL = tot[0] - lastTot[0];
			if (toL) {
				hi = mid-1;
			}
			else lo = mid+1;
		}	
		assert(idx != -1);
		ll = idx+1;
		lastTot = ask(ll);
		while (lastTot[0] + lastTot[1] != need) {
			if (lastTot[0] + lastTot[1] == 0) return ll;
			ll++;
			lastTot = ask(ll);
		}
	}
}

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