Submission #51178

#	Time	Username	Problem	Language	Result	Execution time	Memory
51178		aome	The Big Prize (IOI17_prize)	C++17	97.62 / 100	49 ms	572 KiB

prize

#include <bits/stdc++.h>
#include "prize.h"

using namespace std;

int res;

bool check(vector<int> &tmp) {
	return !tmp[0] && !tmp[1];
}

void cal(int l, int r, int fl, int fr) {
	if (l == r || l + 1 == r || res != -1) return;

	int mid = (l + r) >> 1;
	vector<int> tmp = ask(mid);

	if (check(tmp)) { res = mid; return; }

	if (tmp[0] != fr) cal(mid, r, tmp[0], fr);
	if (tmp[0] != fl) cal(l, mid, fl, tmp[0]);
}

int find_best(int n) {
	res = -1;
	vector<int> l = ask(0);
	vector<int> r = ask(n - 1);

	if (check(l)) return 0;
	if (check(r)) return n - 1;

	cal(0, n - 1, l[0], r[0]);
	return res;
}	

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