Submission #1124486

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124486		NotLinux	The Big Prize (IOI17_prize)	C++20	20 / 100	39 ms	1444 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){
		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]);
	}
	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;
			if(myres[1] == 0)break;
			int l = cur+1 , r = n;
			while(l < r){
				int mid = (l + r) / 2;
				vector < int > midres = query(mid);
				if(check(midres) == 0){
					cur = mid;
					r = mid;
				}
				else if(midres[0] - myres[0])r = mid;
				else l = mid+1;
			}	
			res = query(cur);		
		}
		if(res[0] + res[1] == 0)return cur;
		cur++;
	}
	assert(false);
}

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