Submission #975474

#	Time	Username	Problem	Language	Result	Execution time	Memory
975474		pirhosig	The Big Prize (IOI17_prize)	C++17	20 / 100	39 ms	684 KiB

prize

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



int solve(int low, int upp, int less, int more, int large) {
	if (less + more == large) return 0;

	int mid = (low + upp) / 2;
	auto a = ask(mid);
	int tot = a[0] + a[1];
	if (tot == 0) return mid;

	if (low == upp) return 0;

	int res = 0;
	if (tot == large) {
		if (low < mid) res += solve(low, mid - 1, less, a[1], large);
		if (mid < upp) res += solve(mid + 1, upp, a[0], more, large);
	}
	else {
		int mdx = mid;
		while (mdx++ < upp && tot < large) {
			a = ask(mdx);
			tot = a[0] + a[1];
			if (tot == 0) return mdx;
		}
		if (tot == large) {
			if (low < mid) res += solve(low, mid - 1, less, a[1] + mdx - mid, large);
			if (mdx < upp) res += solve(mdx + 1, upp, a[0], more, large);
		}
		else if (low < mid) res += solve(low, mid - 1, less, more + mdx - mid, large);
	}

	return res;
}


	
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;
		}
	}
	
	int large = 0;
	vector<int> val(450);
	for (int i = 0; i < 450; ++i) {
		auto a = ask(i);
		val[i] = a[0] + a[1];
		if (val[i] == 0) return i;
		large = max(large, val[i]);
	}
	
	int found = 0;
	for (int a : val) if (a != large) found++;
	
	return solve(450, n - 1, found, 0, large);
}

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