Submission #295506

#	Time	Username	Problem	Language	Result	Execution time	Memory
295506		mode149256	The Big Prize (IOI17_prize)	C++14	0 / 100	1 ms	368 KiB

prize

#include <bits/stdc++.h>
#include "prize.h"
using namespace std;
using vi = vector<int>;
int N;

int get(int l, int r, int kiek) {
	// int sqr = (int)sqrt(r - l + 1);
	int m = (l + r) / 2;

	if (kiek <= 0) return -1;

	int st = max(l, m - kiek / 2);

	// ieskom did des [1]

	vi viso(2, 0);
	int ind = 0;

	for (int i = 0; i < kiek + 1 and st + i <= r; ++i)
	{
		vi ans = ask(st + i);

		if (ans[0] == ans[1] and ans[0] == 0)
			return i;

		if (ans[0] + ans[1] >= viso[0] + viso[1]) {
			ind = st + i;
			viso = ans;
		}
	}

	int left = get(l, ind - 1, kiek - viso[1]);
	int right = get(ind + 1, r, kiek - viso[0]);
	if (left != -1) return left;
	else return right;
}

int find_best(int n) {
	N = n;
	// if (n <= 5000) {
	// 	for (int i = 0; i < n; ++i)
	// 	{
	// 		vi ans = ask(i);
	// 		if (ans[0] == ans[1] and ans[0] == 0)
	// 			return i;
	// 	}
	// }

	vi viso(2, 0);
	int ind = 0;

	for (int i = 0; i < 10; ++i) {
		vi ans = ask(i);
		if (ans[0] == ans[1] and ans[0] == 0)
			return i;
		if (ans[0] + ans[1] >= viso[0] + viso[1]) {
			ind = i;
			viso = ans;
		}
	}

	return get(ind + 1, n - 1, viso[1]);
}

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