Submission #294911

#	Time	Username	Problem	Language	Result	Execution time	Memory
294911		VodkaInTheJar	The Big Prize (IOI17_prize)	C++14	20 / 100	51 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;
}
*/
 
auto c = 200;
 
int max_sum; 
int find_best(int n)
{
	for (int i = 0; i < min(n, 600); 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; 
			
			else 
			i++;
		}
		
		else 
		i++; 
	}
}
 
/*
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:66:1: warning: control reaches end of non-void function [-Wreturn-type]
   66 | }
      | ^

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