Submission #294834

#	Time	Username	Problem	Language	Result	Execution time	Memory
294834		VodkaInTheJar	The Big Prize (IOI17_prize)	C++14	0 / 100	122 ms	376 KiB

prize

#include <bits/stdc++.h>
#include "prize.h"
 
using namespace std;
mt19937 random_generator(23799971);

const int maxn = 2e5 + 3; 

int max_sum; 
bool is[maxn];
void f(int l, int r, int how_many, int sub_l, int sub_r)
{
	if (l > r)
	return;
	
	if (how_many == r - l + 1)
	{
		for (int i = l; i <= r; i++)
		is[i] = true; 
		
		return;
	}
	
	if (how_many <= (r - l + 1) * 7 / 8)
	return;
	
	for (;;)
	{
		int idx = l + random_generator() % (r - l + 1);
	    auto curr = ask(idx);
	    
	    if (curr[0] + curr[1] == max_sum)
	    {
			curr[0] -= sub_l;
			curr[1] -= sub_r;
			is[idx] = true;
			
			f(l, idx-1, curr[0], sub_l, sub_r + curr[1] + 1);
			f(idx+1, r, curr[1], sub_l + curr[0] + 1, sub_r);
			break; 
		}
	}
}


int find_best(int n)
{
	for (int i = 1; i <= 100; i++)
	{
		int idx = random_generator() % n;
		auto curr = ask(idx);
		
		max_sum = max(max_sum, curr[0] + curr[1]);
	}
	
	f(0, n-1, n - max_sum, 0, 0);
	
	for (int i = 0; i < n; i++)
	if (!is[i])
	{
		auto curr = ask(i);
		if (curr[0] + curr[1] == 0)
		return i; 
	}
}

Compilation message (stderr)

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

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