Submission #390543

#	Time	Username	Problem	Language	Result	Execution time	Memory
390543		aarr	The Big Prize (IOI17_prize)	C++14	0 / 100	2 ms	456 KiB

prize

#include "prize.h"

#include <bits/stdc++.h>
using namespace std;

int n;
const int N = 200 * 1000 + 5;
pair <int, int> res[N];
bool mark[N];

void ask_save(int k) {
	if (!mark[k]) {
		vector <int> vec = ask(k);
		res[k].first = vec[0];
		res[k].second = vec[1];
	}
	
}

int solve(int s, int e) {
	if (e - s <= 2) {
		return n;
	}
	int md = (s + e) / 2;
	ask_save(md);
	if (res[md].first + res[md].second == 0) {
		return md;
	}
	int ans = n;
	if (res[md] != res[s]) {
		ans = solve(s, md + 1);
		if (ans < n) {
			return ans;
		}
	}
	if (res[md] != res[e]) {
		ans = min(ans, solve(md, e));
	}
	return ans;
}

int find_best(int n) {
	ask_save(0);
	ask_save(n - 1);
	if (res[0].first + res[0].second == 0) {
		return 0;
	}
	if (res[n - 1].first + res[n - 1].second == 0) {
		return n - 1;
	}
	return solve(0, n);
}

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