Submission #410430

#	Time	Username	Problem	Language	Result	Execution time	Memory
410430		Antekb	The Big Prize (IOI17_prize)	C++14	96.93 / 100	76 ms	5516 KiB

prize

#include "prize.h"
#include<bits/stdc++.h>
using namespace std;
const int N=(1<<19);
set<int> S;
vector<vector<int>> V;
vector<int> ask2(int i){
	if(S.find(i)==S.end())V[i]=ask(i), S.insert(i);
	return V[i];
}
int find_best(int n) {
	V.resize(n);
	map<int, int> M;
	for(int i = 0; i < n; ) {
		std::vector<int> res = ask2(i);
		if(res==vector<int>{0, 0})return i;
		auto it=S.lower_bound(i);
		int l=0, r=n-i-1;
		while(V[*it]==res){
			l=*it-i;
			it++;
		}
		if(it!=S.end())r=*it-i;
		if(M[res[0]+res[1]]++>100){	
			while(l<r){
				int m;
				m=(l+r+1)/2;
				vector<int> res2=ask2(i+m);
				if(res2==res)l=m;
				else r=m-1;
			}
			M[res[0]+res[1]]+=l;
			
		}
		i+=l+1;
		
	}
	return 0;
}

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