Submission #622729

#	Time	Username	Problem	Language	Result	Execution time	Memory
622729		pawned	The Big Prize (IOI17_prize)	C++17	92.68 / 100	78 ms	1992 KiB

prize

#include "prize.h"

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

#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;

int N;

ii ans[200005];

set<int> pos;

void query(int n) {
	vi res = ask(n);
	ans[n] = {res[0], res[1]};
}

int most = 0;

void dq(int left, int right) {	// is there a sus in [left, right]?
//	cout<<"at "<<left<<", "<<right<<endl;
	if (left > right)
		return;
	if (ans[left].fi == -1)
		query(left);
	if (ans[right].fi == -1)
		query(right);
	if (ans[left].fi + ans[left].se != most) {
		pos.insert(left);
		dq(left + 1, right);
		return;
	}
	if (ans[right].fi + ans[right].se != most) {
		pos.insert(right);
		dq(left, right - 1);
		return;
	}
	if (ans[left].se == ans[right].se)
		return;
	int mid = (left + right) / 2;
	dq(left, mid);
	dq(mid, right);
}


int find_best(int n) {
	N = n;
/*
	if (N < 10000) {
		for (int i = 0; i < N; i++) {
			vi res = ask(i);
			if (res[0] + res[1] == 0)
				return i;
		}
		return 0;
	}
*/
	for (int i = 0; i < N; i++) {
		ans[i] = {-1, -1};
	}
	for (int i = 0; i < min(N - 1, 500); i++) {
		query(i);
		most = max(most, ans[i].fi + ans[i].se);
	}
//	cout<<"most is "<<most<<endl;
	query(0);
	query(N - 1);
	dq(0, N - 1);
/*
	cout<<"pos: ";
	for (int i : pos)
		cout<<i<<" ";
	cout<<endl;
*/
	for (int i : pos) {
		query(i);
		if (ans[i].fi + ans[i].se == 0)
			return i;
	}
	return -1;
}

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