Submission #1124478

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124478		NotLinux	The Big Prize (IOI17_prize)	C++20	20 / 100	38 ms	1272 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l , int r){
	return rng() % (r-l+1) + l;
}
int find_best(int n) {
	map < int , vector<int>>mpa;
	auto query = [&](int x){
		// cout << "query : " << x << endl;
		if(mpa.count(x))return mpa[x];
		else return mpa[x] = ask(x);
	};
	// find the maximum by random sampling
	const int M = 50;
	int maxi = 0;
	for(int i = 0;i<M;i++){
		vector < int > res = query(rand(0,n-1));
		maxi = max(maxi , res[0] + res[1]);
	}
	// cout << "maxi : " << maxi << endl;
	// cout << "DONE" << endl;
	auto check = [&](vector < int > &a){// check whether it is the biggest one
		return maxi == a[0] + a[1];
	};
	// iterate over the non biggest ones
	int cur = 0;
	while(cur < n){
		vector < int > res = query(cur);
		if(check(res)){// it is one of the biggest ones , make it not
			vector < int > myres = res;
			// cout << "myres : " << myres[0] << " " << myres[1] << endl;
			if(myres[1] == 0)break;
			int l = cur+1 , r = n;
			while(l < r){
				int mid = (l + r) / 2;
				vector < int > midres = query(mid);
				// cout << mid << " midres : " << midres[0] << " " << midres[1] << endl;
				if(check(midres) == 0){
					cur = mid;
					r = mid;
				}
				else if(midres[0] - myres[0])r = mid;
				else l = mid+1;
			}	
			res = query(cur);		
		}
		// cout << "cur : " << cur << endl;
		if(res[0] + res[1] == 0)return cur;
		cur++;
	}
	return -1;
}

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