Submission #294959

#	Time	Username	Problem	Language	Result	Execution time	Memory
294959		VodkaInTheJar	The Big Prize (IOI17_prize)	C++14	90 / 100	95 ms	384 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;
}
*/

const int c = 1000;

int max_sum; 
int find_best(int n)
{
	for (int i = 0; i < min(n, 500); i++)
	{
		auto curr = ask(i);
		if (curr[0] + curr[1] == 0)
		return i;
		
		max_sum = max(max_sum, curr[0] + curr[1]);
	}
	
	for (int i = 0; i < n; i += c)
	{
		int j = min(i + c - 1, n - 1);
		auto first = ask(i), second = ask(j);
		if (first[0] == second[0] && first[1] == second[1])
		continue; 
		
		for (int p = i; p <= j; )
		{
			auto curr = ask(p);
			if (curr[0] + curr[1] == 0)
			return p; 
			
			if (curr[0] + curr[1] != max_sum)
			{
				p++;
				continue;
			}
			
			int low = p + 1, high = j;
			while (low < high)
			{
				int mid = (low + high) / 2; 
				auto temp = ask(mid);
				
				if (temp[0] == curr[0] && temp[1] == curr[1])
				low = mid + 1; 
				
				else 
				high = mid;
			}
			
			p = low; 
		}
	}
}
 
/*
int main()
{
	cin >> m;
	for (int i = 0; i < m; i++)
	cin >> a[i];
	
	cout << find_best(m) << endl; 
}
*/

Compilation message (stderr)

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

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