Submission #1028755

#	Time	Username	Problem	Language	Result	Execution time	Memory
1028755		parsadox2	The Big Prize (IOI17_prize)	C++17	20 / 100	605 ms	3848 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 sq = Sq(n);
	int mx = 0;
	for(int i = 0 ; i < min(n , sq + 2) ; i++)
	{
		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)
		{
			int mid = (low + high) >> 1;
			int id = all[mid];
			auto now = ask(id);
			if(now[0] + now[1] != mx)
			{
				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])
	{
		auto now = ask(i);
		if(now[0] + now[1] == 0)
			return i;
	}
	for(int i = 0 ; i < n ; i++)
	{
		auto now = ask(i);
		if(now[0] + now[1] == 0)
			return i;
	}	
}

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

Compilation message (stderr)

prize.cpp: In function 'int Solve()':
prize.cpp:71:1: warning: control reaches end of non-void function [-Wreturn-type]
   71 | }
      | ^

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