Submission #799136

#	Time	Username	Problem	Language	Result	Execution time	Memory
799136		LittleCube	The Big Prize (IOI17_prize)	C++17	20 / 100	388 ms	8696 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
using namespace std;

namespace
{
	int n, bad = 0;
	vector<int> res[200005];
	int bit[200005];
};

void modify(int pos)
{
	pos++;
	for (int i = pos; i <= n; i += (i & -i))
		bit[i]++;
}

int query(int pos)
{
	int ans = 0;
	pos++;
	for (int i = pos; i ; i -= (i & -i))
		ans += bit[i];
	return ans;
}

pii how(int k)
{
	if (res[k].size() == 0)
		res[k] = ask(k);
	return pii(res[k][0], res[k][1]);
}

int find_best(int n)
{
	::n = n;
	vector<int> remain;
	vector<int> v;
	for (int i = 0; i < n; i++)
		remain.emplace_back(i);
	for (int i = 0; i < min(n, 601); i++)
		bad = max(bad, how(i).F + how(i).S);

	for (int t = 0; t <= 600; t++)
	{
		int l = 0, r = remain.size(), mid;
		while (r - l > 1)
		{
			mid = (l + r) / 2;
			if (how(mid).F + how(mid).S < bad)
			{
				l = mid;
				goto oyes;
			}
			else if (how(mid).F > query(mid))
				r = mid;
			else
				l = mid;
		}
	oyes:
		if (how(l).F + how(l).S < bad)
		{
			v.emplace_back(l);
			vector<int> nxt;
			for (int i : remain)
				if (i != l)
					nxt.emplace_back(i);
			modify(l);
			remain = nxt;
		}
		else
			break;
	}
	for (int i : v)
		if (how(i) == pii(0, 0))
			return i;
	return 0;
}

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