Submission #407007

#	Time	Username	Problem	Language	Result	Execution time	Memory
407007		ja_kingy	The Big Prize (IOI17_prize)	C++14	100 / 100	74 ms	6060 KiB

prize

#include "prize.h"
#include <iostream>
using namespace std;

vector<int> cache[200000];
int ans, cnt, done[200000], n;
vector<int> askc(int x) {
	if (!done[x]) {
		done[x] = 1;
		cache[x] = ask(x);
	}
	return cache[x];
}

void find(int l, int r, int el, int er) {
	if (r < l) return;
	if (cnt == el + er) return;
	int m = l+r>>1;
	int x = m;
	vector<int> res;
	for (; x <= r; x++) {
		res = askc(x);
		if (res[0] == 0 && res[1] == 0) ans = x;
		if (res[0] + res[1] > cnt) {
			cnt = res[0] + res[1];
			find(0, n-1, 0, 0);
		}
		if (res[0] + res[1] == cnt) break;
	}
	if (l != r) {
		find(l, m-1, el, x - m + res[1]);
		find(x+1, r, res[0], er);
	}
}

int find_best(int _n) {
	cnt = 1;
	n = _n;
	find(0, n-1, 0, 0);
	return ans;
}

Compilation message (stderr)

prize.cpp: In function 'void find(int, int, int, int)':
prize.cpp:18:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   18 |  int m = l+r>>1;
      |          ~^~

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