Submission #139969

#	Time	Username	Problem	Language	Result	Execution time	Memory
139969		arthurconmy	The Big Prize (IOI17_prize)	C++14	90 / 100	112 ms	2304 KiB

prize

#include <bits/stdc++.h>

#ifndef ARTHUR_LOCAL
	#include "prize.h"
#endif

using namespace std;

// NB: ask(i) returns a two-elem vector<int>

const int MAXN=200000;

bool asked[MAXN];
pair<int,int> answers[MAXN];

#ifdef ARTHUR_LOCAL
	vector<int> real_deal;

	vector<int> ask(int n)
	{
		int ans1=0;
		int ans2=0;

		for(int i=0; i<n; i++)
		{
			if(real_deal[i]<real_deal[n]) ans1++;
		}

		for(int i=n; i<8; i++)
		{
			if(real_deal[i]<real_deal[n]) ans2++;
		}

		return {ans1,ans2};
	}
#endif

pair<int,int> get_ans(int n)
{	
	//cout << n << endl;

	if(asked[n]) return answers[n];

	// cout << "Q!" << endl;

	asked[n]=1;
	vector<int> cur = ask(n);
	answers[n] = {cur[0],cur[1]};
	return answers[n];
}	

int find_best(int n) 
{
	// query 30 random places in order to determine the minimum thing

	random_device rd;  
    mt19937 gen(rd()); 
    uniform_int_distribution<> dis(1,1000000000);

	int max_side=0;

	for(int i=0; i<2000; i++) // should be less than 2**(-30) of failure to find the right value
	{
		pair<int,int> cur = get_ans(dis(gen)%n);
		max_side = max(max_side,cur.first+cur.second);
	}

	int left = 0;
	int right = n-1;

	while(true)
	{
		pair<int,int> cur = get_ans(left);

		if(cur.first + cur.second == 0) return left;
		if(cur.first + cur.second == max_side) break;

		left++;
	}

	while(true)
	{
		pair<int,int> cur = get_ans(right);

		if(cur.first + cur.second == 0) return right;
		if(cur.first + cur.second == max_side) break;

		right--;
	}

	//cout << left << " " << right << endl;

	vector<pair<int,int>> I = {make_pair(left,right)};

	while(true)
	{
		vector<pair<int,int>> new_I;

		for(auto i:I)
		{
			int left = i.first;
			int right = i.second;

			// cout << left << " " << right << endl;

			int lmid = int((left+right)/2);
			int rmid = lmid + 1;

			bool do_left=1;
			bool do_right=1;

			while(true)
			{
				pair<int,int> cur = get_ans(lmid);

				if(cur.first + cur.second == 0) return lmid;
				if(cur.first + cur.second == max_side) break;

				if(cur.first == 0) do_left=0;
				if(cur.second == 0) do_right=0;

				// if(get_ans(lmid).first == get_ans(left).first) break;

				lmid--;
			}

			while(true)
			{
				pair<int,int> cur = get_ans(rmid);

				if(cur.first + cur.second == 0) return rmid;
				if(cur.first + cur.second == max_side) break;

				if(cur.first == 0) do_left=0;
				if(cur.second == 0) do_right=0;

				// if(get_ans(right).first == get_ans(rmid).first) break;

				rmid++;
			}

			//cout << "LR: " << lmid << " " << rmid << endl;

			if(do_left && get_ans(lmid).first > get_ans(left).first) new_I.push_back({left,lmid});
			if(do_right && get_ans(right).first > get_ans(rmid).first) new_I.push_back({rmid,right});
		}

		I = new_I;
	}
}

#ifdef ARTHUR_LOCAL

	int main()
	{
		//cout << sqrt(200000) << endl;

		real_deal = {1,2,2,3,3,3,3,3};

		do
		{
			for(int i=0; i<8; i++)
			{
				asked[i]=0;
			}

			//for(auto i:real_deal) cout << i << " ";
			cout << endl << find_best(8) << endl;

		} while(next_permutation(real_deal.begin(),real_deal.end()));
	}
#endif

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