Submission #799328

#	Time	Username	Problem	Language	Result	Execution time	Memory
799328		LittleCube	The Big Prize (IOI17_prize)	C++17	97.62 / 100	201 ms	379540 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 in[200005];
	struct BIT
	{
		int bit[200005];
		void init()
		{
			for (int i = 0; i <= n; i++)
				bit[i] = 0;
		}
		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;
		}
	} bit[505];
};

pii how(int k)
{
	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);
	for (int i = how(l).F + how(l).S + 1; i <= bad; i++)
		bit[i].modify(l);
}

void count(vector<int> v, int left, int rem)
{
	if (rem == 0)
		return;
	if (rem == v.size())
	{
		for (auto i : v)
			large.emplace_back(i);
		return;
	}
	bool proceed = 1;
	int cur, mx = 0, mi = n;
	while (proceed)
	{
		int k = v.size() / 2;
		cur = v[k];
		mx = max(mx, v[k]), mi = min(mi, 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> l(v.begin(), v.begin() + k),
		r(v.begin() + k + 1, v.end());
		
	count(l, left, how(cur).F - left - (v[k] - mi));
	count(r, how(cur).F + (mx - v[k]), rem - (how(cur).F - left) - (mx - v[k]));
}

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

	vector<int> remain;
	for (int i = 0; i < n; i++)
		remain.emplace_back(i);

	for (int i = n / 2 - 240; i < n / 2 + 240; i++)
		bad = max(bad, how(i).F + how(i).S);
	assert(bad <= 480);
	for (int t = 0; t <= bad; t++)
		bit[t].init();

	count(remain, 0, bad);

	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:61:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |  if (rem == v.size())
      |      ~~~~^~~~~~~~~~~
prize.cpp: At global scope:
prize.cpp:14:6: warning: '{anonymous}::in' defined but not used [-Wunused-variable]
   14 |  int in[200005];
      |      ^~

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