Submission #800896

#	Time	Username	Problem	Language	Result	Execution time	Memory
800896		LittleCube	The Big Prize (IOI17_prize)	C++17	100 / 100	45 ms	8672 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];
};

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

vector<int> large;

void update(int l)
{
	large.emplace_back(l);
}

void count(vector<int> v, int l, int r)
{
	int rem = how(r).F - how(l).F - ((r - l - 1) - (int)v.size());
	if (rem == 0)
		return;
	if (rem == v.size())
	{
		for (auto i : v)
			large.emplace_back(i);
		return;
	}

	bool proceed = 1;
	int cur;
	while (proceed)
	{
		if (v.empty())
			return;
		int k = v.size() / 2;
		cur = v[k];
		if (how(cur).F + how(cur).S < bad)
		{
			update(v[k]);
			v.erase(v.begin() + k);
		}
		else
			proceed = 0;
	}
	int k = v.size() / 2;
	vector<int> left(v.begin(), v.begin() + k),
		right(v.begin() + k + 1, v.end());

	count(left, l, cur);
	count(right, cur, r);
}

vector<int> cnt;

void count(int l, int r, int rem)
{
	if (rem <= 0)
		return;
	rem--;
	int m = (l + r) / 2, lrem = rem / 2;
	bad = max(bad, how(m).F + how(m).S);
	cnt.emplace_back(m);
	count(l, m - 1, lrem);
	count(m + 1, r, rem - lrem);
}

int find_best(int n)
{
	::n = n;
	if (n <= 5000)
		for (int i = 0; i < n; i++)
			if (how(i).F + how(i).S == 0)
				return i;

	count(0, n - 1, 480);
	assert(bad <= 480);
	int l = -1, last = 0;
	vector<int> v;
	sort(cnt.begin(), cnt.end());
	cnt.emplace_back(n);
	for (int r : cnt)
	{
		for (int i = last; i < r; i++)
			v.emplace_back(i);
		last = r + 1;
		if (how(r).F + how(r).S < bad)
			update(r);
		else
		{
			count(v, l, r);
			l = r;
			v.clear();
		}
	}

	for (int i : large)
		cerr << i << ' ';
	cerr << '\n';

	for (int i : large)
		if (how(i) == pii(0, 0))
			return i;
	return 0;
}

Compilation message (stderr)

prize.cpp: In function 'void count(std::vector<int>, int, int)':
prize.cpp:39:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |  if (rem == v.size())
      |      ~~~~^~~~~~~~~~~

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