Submission #797510

#	Time	Username	Problem	Language	Result	Execution time	Memory
797510		alvingogo	The Big Prize (IOI17_prize)	C++14	20 / 100	58 ms	1728 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;
vector<int> query(int x){
	if(m.find(x)==m.end()){
		m[x]=ask(x);
		if(m[x][0]+m[x][1]==k){
			c++;
		}
		else{
		}
		return m[x];
	}
	return m[x];
}
int find_best(int n) {
	for(int i=0;i<min(n,470);i++){
		auto q=query(i);
		k=max(k,q[0]+q[1]);
	}
	m[-1]={0,k};
	m[n]={k,0};
	set<int> s;
	queue<pair<int,int> > q;
	q.push({-1,n});
	while(q.size()){
		auto h=q.front();
		q.pop();
		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: 0 / 80