Submission #799153

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

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, 501); i++)
		bad = max(bad, how(i).F + how(i).S);
	assert(bad <= 500);
	for (int t = 0; t <= bad; t++)
		bit[t].init();
	for (int t = 0; t <= 500; t++)
	{
		int l = 0, r = remain.size(), m, mid;
		while (r - l > 1)
		{
			m = (l + r) / 2;
			mid = remain[m];
			if (how(mid).F + how(mid).S < bad)
			{
				l = m;
				goto oyes;
			}
			else if (how(mid).F > bit[min(bad, how(mid).F + how(mid).S)].query(mid))
				r = m;
			else
				l = m;
		}
	oyes:
		if(l >= remain.size())
			break;
		l = remain[l];
		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);
			for (int i = how(l).F + how(l).S + 1; i <= bad; i++)
				bit[i].modify(l);
			remain = nxt;
		}
		else
			break;
	}
	for (int i : v)
		cerr << i << ' ';
	cerr << '\n';
	for (int i : v)
		if (how(i) == pii(0, 0))
			return i;
	return 0;
}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:77:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |   if(l >= remain.size())
      |      ~~^~~~~~~~~~~~~~~~

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