Submission #1028735

#	Time	Username	Problem	Language	Result	Execution time	Memory
1028735		parsadox2	The Big Prize (IOI17_prize)	C++17	20 / 100	860 ms	2208 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10;
int n;
bool marked[N] , dead[N];

int Sq(int val)
{
	for(int i = 1 ; i <= val ; i++)  if(i * i >= val)
		return i;
	return -1;
}

void Solve()
{
	vector <int> all;
	for(int i = 0 ; i < n ; i++)  if(!dead[i])
		all.push_back(i);
	int m = all.size() , sq = Sq(m);
	if(m == 1)
		return;
	int mx = 0;
	for(int i = 0 ; i < sq ; i++)
	{
		auto now = ask(all[i]);
		mx = max(mx , now[0] + now[1]);
	}
	for(auto u : all)
		marked[u] = false;
	for(int asd = 0 ; asd < mx ; asd++)
	{
		all.clear();
		for(int i = 0 ; i < n ; i++)  if(!dead[i] && !marked[i])
			all.push_back(i);
		m = all.size();
		int low = -1 , high = m;
		while(high - low > 1)
		{
			int mid = (low + high) >> 1;
			int id = all[mid];
			auto now = ask(id);
			if(now[0] + now[1] != mx)
			{
				marked[id] = true;
				break;
			}
			dead[id] = true;
			for(int i = 0 ; i < id ; i++)  if(!dead[i] && marked[i])
				now[0]--;
			if(now[0] == 0)
				low = mid;
			else
				high = mid;
		}
	}
	for(int i = 0 ; i < n ; i++)  if(!marked[i])
		dead[i] = true;
	Solve();
}

int find_best(int nn) {
	n = nn;
	Solve();
	for(int i = 0 ; i < n ; i++)  if(!dead[i])
		return i;
	return -1;
}

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