Submission #54235

#	Time	Username	Problem	Language	Result	Execution time	Memory
54235		radoslav11	The Big Prize (IOI17_prize)	C++14	97.60 / 100	116 ms	31676 KiB

prize

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

using namespace std;
template<class T, class T2> inline int chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline int chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const int MAXN = (1 << 20);

vector<int> memo[MAXN];
int Q = 0;
bool stop;
bool dummy[MAXN];

vector<int> query(int i) 
{
	if(!memo[i].empty()) return memo[i];
	if(stop || dummy[i]) return vector<int>(2, 1e9);
	
	memo[i] = ask(i), Q++;
	if(Q == 10000) assert(false);
	return memo[i];
}

int n;

void rec(int l, int r)
{
	if(r < l) return;

	if(query(l - 1)[0] + query(l - 1)[1] == 0) stop = 1;	
	if(query(r + 1)[0] + query(r + 1)[1] == 0) stop = 1;

	if(query(l - 1)[0] == 0)
		for(int p = l - 2; p >= 0; p--)
		{
			if(dummy[p]) break;
			dummy[p] = 1;
		}

	if(query(r + 1)[1] == 0)
		for(int p = r + 2; p < n; p++)
		{
			if(dummy[p]) break;
			dummy[p] = 1;
		}

	if(query(r + 1)[0] == 0)
		for(int p = r; p >= 0; p--)
		{
			if(dummy[p]) break;
			dummy[p] = 1;
		}
	
	if(query(l - 1)[1] == 0)
		for(int p = l; p < n; p++)
		{
			if(dummy[p]) break;
			dummy[p] = 1;
		}
	
	if(query(l - 1) == query(r + 1))
	{
		for(int i = l; i <= r; i++)
			memo[i] = query(l - 1);
		return;
	}

	int mid = (l + r) >> 1; 
	if(query(mid)[0] + query(mid)[1] == 0) stop = 1;
	if(query(l - 1) == query(mid))
		for(int i = l; i < mid; i++)
			memo[i] = query(mid);
	else
		rec(l, mid - 1);

	if(query(mid) == query(r + 1))
		for(int i = mid + 1; i <= r; i++)
			memo[i] = query(mid);
	else
		rec(mid + 1, r);
}

int find_best(int n) 
{	
	::n = n;
	rec(1, n - 2);
	for(int i = 0; i < n; i++)
		if(query(i)[0] + query(i)[1] == 0)
			return i;

	return -1;
}

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