Submission #838105

#	Time	Username	Problem	Language	Result	Execution time	Memory
838105		Johann	The Big Prize (IOI17_prize)	C++14	100 / 100	49 ms	11376 KiB

prize

#include "prize.h"
#include "bits/stdc++.h"
using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

vvi Qu;
vi query(int i)
{
	if (Qu[i][0] == -1)
		Qu[i] = ask(i);
	return Qu[i];
}
set<int> sums;
int reference;
vi interesting;

int cnt;
int r;
void resolve(int l)
{
	if (r - l == 0)
		return;
	vi tmp = query(l);
	if (tmp[0] + tmp[1] != reference)
	{
		resolve(l + 1);
		interesting.push_back(l);
		++cnt;
	}
	else
	{
		while (tmp[1] > cnt)
			resolve((l + r) / 2);
	}
	r = l;
}

int find_best(int n)
{
	Qu.assign(n, {-1, -1});

	if (n <= 5000)
	{ // query everything
		for (int i = 0; i < n; i++)
		{
			std::vector<int> res = ask(i);
			if (res[0] + res[1] == 0)
				return i;
		}
	}

	int j = 0;
	while (n / (1 << (j + 1)) >= 500)
		++j;

	sums.clear();
	int i;
	for (i = 0; i < n; i += (1 << j))
	{
		vi tmp = query(i);
		sums.insert(tmp[0] + tmp[1]);
	}
	reference = *sums.rbegin();

	cnt = 0;
	if (i >= n)
		i -= (1 << j);
	r = n;
	while (i >= 0)
	{
		resolve(i);
		i -= (1 << j);
	}

	for (int x : interesting)
	{
		vi tmp = query(x);
		if (tmp[0] + tmp[1] == 0)
			return x;
	}

	return 0;
}

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