Submission #294905

#	Time	Username	Problem	Language	Result	Execution time	Memory
294905		VodkaInTheJar	The Big Prize (IOI17_prize)	C++14	20 / 100	104 ms	1772 KiB

prize

#include <bits/stdc++.h>
#include "prize.h"
 
using namespace std;
mt19937 random_generator(chrono::steady_clock::now().time_since_epoch().count());
 
const int maxn = 2e5 + 3; 
 
/*
int m; 
int a[maxn];
vector <int> ask(int x)
{
	vector <int> ans;
	ans.resize(2);
	ans[0] = ans[1] = 0; 
	
	for (int i = 0; i < x; i++)
	if (a[i] < a[x])
	ans[0]++;
	
	for (int i = x + 1; i < m; i++)
	if (a[i] < a[x])
	ans[1]++;
	
	return ans;
}
*/
 
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) * 2 / 3)
	return;
	
	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, idx - l - curr[0], sub_l, sub_r + curr[1]);
		f(idx+1, r, r - idx - curr[1], sub_l + curr[0], sub_r);
	}
	
	else 
	{
		if (curr[0] + curr[1] != 0)
		is[idx] = true;
		
		f(l, r, how_many, sub_l, sub_r);
	}
}
 
 
int find_best(int n)
{
	for (int i = 0; i < min(n, 450); i++)
	{
		auto curr = ask(i);
		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; 
	}
	
	return -1; 
}
 
/*
int main()
{
	cin >> m;
	for (int i = 0; i < m; i++)
	cin >> a[i];
	
	cout << find_best(m) << endl; 
}
*/

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