Submission #975442

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

prize

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



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;
	for (int i = 0; i < 450; ++i) {
		auto a = ask(i);
		large = max(large, a[0] + a[1]);
	}

	int low = 0;
	for (int i = 1; i <= large; ++i) {
		int upp = n - 1;
		while (low < upp) {
			int mid = (low + upp) / 2;
			auto a = ask(mid);
			int tot = a[0] + a[1];
			if (tot == 0) return mid;
			if (tot == large) {
				if (a[0] < i) low = mid + 1;
				else upp = mid - 1;
			}
			else {
				int dvm = mid;
				while (tot < large) {
					dvm--;
					a = ask(dvm);
					tot = a[0] + a[1];
					if (tot == 0) return dvm;
				}
				if (a[0] + dvm - mid >= i) i += dvm - mid - 1;
				else low = mid + 1;
			}
		}
		auto a = ask(low);
		if (a[0] + a[1] == 0) return low;
		low++;
	}

	return -1;
}

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