Submission #294929

#	Time	Username	Problem	Language	Result	Execution time	Memory
294929		VodkaInTheJar	The Big Prize (IOI17_prize)	C++14	90 / 100	74 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 = 500;

int max_sum; 
int find_best(int n)
{
	for (int i = 0; i < min(n, 500); i++)
	{
		auto curr = ask(i);
		max_sum = max(max_sum, curr[0] + curr[1]);
	}
	
	for (int i = 0; i < n; )
	{
		auto curr = ask(i);
		if (curr[0] + curr[1] == 0)
		return i; 
		
		if (curr[0] + curr[1] != max_sum)
		{
			i++;
			continue;
		}
		
		if (i + c < n)
		{
			auto temp = ask(i+c);
			if (temp[0] == curr[0] && temp[1] == curr[1])
			{
				i += c + 1; 
				continue;
			}
		}
		
		int low = i+1, high = min(n-1, i+c); 
		while (low < high)
		{
			int mid = (low + high) / 2;
			auto temp = ask(mid);
			
			if (temp[0] != curr[0] || temp[1] != curr[1])
			high = mid;
			
			else 
			low = mid + 1; 
		}
		
		i = 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:78:1: warning: control reaches end of non-void function [-Wreturn-type]
   78 | }
      | ^

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