Submission #1028950

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

prize

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

using namespace std;

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

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

int Solve()
{
	int Q = 0;
	int sq = Sq(n);
	int mx = 0;
	for(int i = 0 ; i < min(n , sq + 10) ; i++)
	{
		Q++;
		auto now = ask(i);
		mx = max(mx , now[0] + now[1]);
	}
	for(int asd = 0 ; asd < mx ; asd++)
	{
		vector <int> all;
		int tmp = 0;
		for(int i = 0 ; i < n ; i++) if(!dead[i])
		{
			if(marked[i])
				tmp++;
			else
			{
				cnt[i] = tmp;
				all.push_back(i);
			}
		}
		int low = -1 , high = all.size();
		while(high - low > 1)
		{
			Q++;
			int mid = (low + high) >> 1;
			int id = all[mid];
			auto now = ask(id);
			//cout << low << " " << high << " " << mid << endl;
			if(now[0] + now[1] != mx)
			{
				//cout << id << "! " << endl;
				marked[id] = true;
				break;
			}
			now[0] -= cnt[id];
			if(now[0] != 0)
				high = mid;
			else
				low = mid;
			dead[id] = true;
		}
	}
	for(int i = 0 ; i < n ; i++)  if(marked[i])
	{
		Q++;
		auto now = ask(i);
		if(now[0] + now[1] == 0)
			return i;
	}
	return -1;
}

int find_best(int nn) {
	n = nn;
	if(n == 1)
		return 0;
	return Solve();
}

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