Submission #797542

#	Time	Username	Problem	Language	Result	Execution time	Memory
797542		alvingogo	The Big Prize (IOI17_prize)	C++14	96.31 / 100	50 ms	1044 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;

map<int,vector<int> > m;
int c=0,k=0;
set<int> s;
vector<int> query(int x){
	if(m.find(x)==m.end()){
		m[x]=ask(x);
		return m[x];
	}
	return m[x];
}
mt19937 rnd(43243214);
int find_best(int n) {
	if(n<=5000){
		for(int i=0;i<n;i++){
			auto h=query(i);
			if(h[0]==0 && h[1]==0){
				return i;
			}
		}
	}
	for(int i=0;i<490;i++){
		k=max(k,query(i)[0]+query(i)[1]);
	}
	m[-1]={0,k};
	m[n]={k,0};
	queue<pair<int,int> > q;
	q.push({-1,n});
	while(q.size()){
		auto h=q.front();
		q.pop();
		int cz=0;
		for(auto it=s.lower_bound(h.fs);(*it)<h.sc;it++){
			cz++;
		}
		if(query(h.fs)==query(h.sc)){
			continue;
		}
		int x=(h.fs+h.sc)/2;
		int flag=0;
		for(int i=x;i>h.fs;i--){
			auto y=query(i);
			if(y[0]+y[1]==k){
				q.push({i,h.sc});
				q.push({h.fs,i});
				flag=1;
				break;
			}
			else{
				s.insert(i);
			}
		}
		if(flag==0){
			for(int i=x+1;i<h.sc;i++){
				auto y=query(i);
				if(y[0]+y[1]==k){
					q.push({i,h.sc});
					flag=1;
					break;
				}
				else{
					s.insert(i);
				}
			}
		}
	}
	for(auto h:s){
		if(query(h)[0]==0 && query(h)[1]==0){
			return h;
		}
	}
	return 0;
}

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