Submission #1156009

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156009		yellowtoad	The Big Prize (IOI17_prize)	C++20	100 / 100	14 ms	5260 KiB

prize

#include <iostream>
#include <vector>
#define f first
#define s second
using namespace std;

std::vector<int> ask(int i);

vector<int> res, dp[200010];
int ans, maxx, pos;
vector<pair<int,int>> rng;

void solve(int l, int r) {
	if (l > r) return;
	if (dp[l-1] == dp[r+1]) return;
	int mid = (l+r)/2, ll, rr;
	dp[mid] = ask(mid-1);
	if (dp[mid][0]+dp[mid][1] == 0) ans = mid-1;
	if (dp[mid][0]+dp[mid][1] == maxx) {
		solve(l,mid-1);
		solve(mid+1,r);
	} else {
		ll = mid-1;
		while (ll >= l) {
			dp[ll] = ask(ll-1);
			if (dp[ll][0]+dp[ll][1] == 0) ans = ll-1;
			if (dp[ll][0]+dp[ll][1] == maxx) break;
			ll--;
		}
		solve(l,ll-1);
		rr = mid+1;
		while (rr <= r) {
			dp[rr] = ask(rr-1);
			if (dp[rr][0]+dp[rr][1] == 0) ans = rr-1;
			if (dp[rr][0]+dp[rr][1] == maxx) break;
			rr++;
		}
		solve(rr+1,r);
	}
}

int find_best(int n) {
	if (n <= 5000) {
		for (int i = 0; i < n; i++) {
			res = ask(i);
			if (res[0]+res[1] == 0) return i;
		}
	}
	rng.push_back({-1,0});
	for (int i = 1; i <= 500; i++) {
		pos += (n-499)/500;
		rng.back().s = pos;
		rng.push_back({pos,0});
		dp[pos+1] = ask(pos);
		maxx = max(maxx,dp[pos+1][0]+dp[pos+1][1]);
	}
	rng.back().s = n;
	dp[0] = {0,maxx};
	dp[n+1] = {maxx,0};
	for (int i = 0; i < rng.size(); i++) {
		int ll = rng[i].f, rr = rng[i].s;
		while ((ll < rr-1) && (dp[ll+1][0]+dp[ll+1][1] != maxx)) {
			ll++;
			dp[ll+1] = ask(ll);
			if (dp[ll+1][0]+dp[ll+1][1] == 0) return ll;
		}
		while ((ll < rr-1) && (dp[rr+1][0]+dp[rr+1][1] != maxx)) {
			rr--;
			dp[rr+1] = ask(rr);
			if (dp[rr+1][0]+dp[rr+1][1] == 0) return rr;
		}
		solve(ll+2,rr);
	}
	return ans;
}

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