Submission #975507

#	Time	Username	Problem	Language	Result	Execution time	Memory
975507		pirhosig	The Big Prize (IOI17_prize)	C++17	100 / 100	30 ms	600 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> ii;



int solve(int low, int upp, ii a, ii b) {
	while (a.first + a.second != b.first + b.second) {
		if (a.first + a.second < b.first + b.second) {
			low++;
			if (low < upp) {
				auto qres = ask(low);
				a = {qres[0], qres[1]};
				if (a.first + a.second == 0) return low;
			}
			else a = b;
		}
		else {
			upp--;
			if (low < upp) {
				auto qres = ask(upp);
				b = {qres[0], qres[1]};
				if (b.first + b.second == 0) return upp;
			}
			else b = a;
		}
	}
	if (a.first == b.first) return 0;
	int mid = (low + upp) / 2;
	auto cres = ask(mid);
	ii c = {cres[0], cres[1]};
	if (c.first + c.second == 0) return mid;
	return solve(low, mid, a, c) + solve(mid, upp, c, b);
}


	
int find_best(int n) {
	if (n < 5000) {
		for (int i = 0; i < n; ++i) {
			auto a = ask(i);
			if (a[0] + a[1] == 0) return i;
		}
	}

	auto qres = ask(0);
	ii a = {qres[0], qres[1]};
	if (a.first + a.second == 0) return 0;
	qres = ask(n - 1);
	ii b = {qres[0], qres[1]};
	if (b.first + b.second == 0) return n - 1;
	return solve(0, n - 1, a, b);
}

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