Submission #282430

#	Time	Username	Problem	Language	Result	Execution time	Memory
282430		Noam13	The Big Prize (IOI17_prize)	C++14	100 / 100	63 ms	1132 KiB

prize

#include <bits/stdc++.h>
#include "prize.h"
#define vi vector<int>
#define vvi vector<vi>
#define vb vector<bool>
#define vvb vector<vb>
#define ii pair<int, int>
#define x first
#define y second
#define vii vector<ii>
#define pb push_back
#define all(x) x.begin(), x.end()
#define loop(i,s,e) for(int i=s;i<e;++i)
#define chkmax(a,b) a = max(a,b)
#define chkmin(a,b) a = min(a,b)
using namespace std;

map<int, ii> qur;
int cnt = 0, maxcnt = 9999;
ii myask(int i){
	//cout<<"QUR: "<<i<<endl;
	if (qur.find(i)!=qur.end()) return qur[i];
	if (cnt++==maxcnt) loop(j,0,1) j--;
	vi res = ask(i);
	return qur[i] = {res[0], res[1]};
}
int mrand(){
	return rand() ^ (rand()<<14);
}
int find_best(int n) {
	cnt = 0; qur.clear();
	int worst = 0;
	set<int> ss; //free querys
	loop(i,0,480){
		int ind = abs(mrand())%n;
		ii res = myask(ind);
		chkmax(worst, res.x+res.y);
		if (res.x+res.y==0) return ind;
		ss.insert(ind);
	}
	loop(i,0,n){
		ii res = myask(i);
		if (res.x+res.y!=worst){
			if (res.x+res.y==0) return i;
			continue;
		}
		int l = i+1, r = n, mid, ans=-1;
		while(l<r){
			mid = (l+r) / 2;
			auto it = ss.lower_bound(l);
			if (it!=ss.end() && *it<r) mid = *it;
			else ss.insert(mid);
			//cout<<"HI: "<<i<<" "<<mid<<endl;
			ii tmp = myask(mid);
			if (tmp.x+tmp.y==0) return mid;
			if (tmp.x+tmp.y!=worst) ans = mid, r = mid;
			else{
				if (tmp.x > res.x) r = mid;
				else l = mid + 1;
			}
		}
		if (ans==-1) break;
		//cout<<"I: "<<i<<" "<<ans<<endl;
		i = ans;
	}
	return 0;
}
/*
clear
g++ prize.cpp grader.cpp -o a ; ./a
8
3 2 3 3 3 2 3 1
*/

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