Submission #1060628

#	Time	Username	Problem	Language	Result	Execution time	Memory
1060628		TAhmed33	The Big Prize (IOI17_prize)	C++98	100 / 100	32 ms	2132 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
//#include "grader.cpp"
pair <int, int> memo[200001];
int ans;
pair <int, int> get (int x) {
	if (memo[x].first != -1) {
		return memo[x];
	}
	auto h = ask(x);
	pair <int, int> g = {h[0], h[1]};
	if (g.first + g.second == 0) {
		ans = x;
	}
	return memo[x] = g;
}
void solve (int l, int r) {
	if (l == r) {
		get(l);
		return;
	}
	auto less = [&] (int x, int y) -> bool {
		return get(x).first + get(x).second < get(y).first + get(y).second;
	};
	while (less(l, r) || less(r, l)) {
		while (less(l, r)) l++;
		while (less(r, l)) r--;
	}
	if (get(l).second == get(r).second) {
		return;
	}
	int mid = (l + r) / 2;
	solve(l, mid); solve(mid, r);
}
int find_best (int n) {
	ans = -1;
	for (int i = 0; i < n; i++) {
		memo[i] = {-1, -1};
	}
	solve(0, n - 1);
	return ans;
}

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