Submission #622734

#	Time	Username	Problem	Language	Result	Execution time	Memory
622734		pawned	The Big Prize (IOI17_prize)	C++17	0 / 100	7 ms	1836 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;

int most2 = 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);
}

map<int, int> conv;

set<int> final;

void dq2(int left, int right) {	// is there a sus in [conv[left], conv[right]]?
//	cout<<"at "<<conv[left]<<", "<<conv[right]<<endl;
	if (conv[left] > conv[right])
		return;
	if (ans[conv[left]].fi == -1)
		query(conv[left]);
	if (ans[conv[right]].fi == -1)
		query(conv[right]);
	if (ans[conv[left]].fi + ans[conv[left]].se != most2) {
		final.insert(conv[left]);
		dq(conv[left] + 1, conv[right]);
		return;
	}
	if (ans[conv[right]].fi + ans[conv[right]].se != most2) {
		final.insert(conv[right]);
		dq(conv[left], conv[right] - 1);
		return;
	}
	if (ans[conv[left]].se == ans[conv[right]].se)
		return;
	int mid = (conv[left] + conv[right]) / 2;
	dq(conv[left], mid);
	dq(mid, conv[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, 450); 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;
*/
	int counter = 0;
	for (int i : pos) {
		most2 = max(most2, ans[i].fi + ans[i].se);
		conv[counter] = i;
		counter++;
	}
	dq2(0, pos.size() - 1);
	for (int i : final) {
		query(i);
		if (ans[i].fi + ans[i].se == 0)
			return i;
	}
	return -1;
}

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