Submission #348306

#	Time	Username	Problem	Language	Result	Execution time	Memory
348306		jamielim	The Big Prize (IOI17_prize)	C++14	0 / 100	124 ms	2512 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
using namespace std;

pair<int,int> memo[200005];
set<pair<int,int> > s;

pair<int,int> qry(int x){
	if(memo[x].first!=-1)return memo[x];
	vector<int> v=ask(x);
	s.insert(make_pair(v[0],x));
	return memo[x]=make_pair(v[0],v[1]);
}

int find(int x){
	auto it=s.lower_bound(make_pair(x,-1));
	return it->second;
}

int find_best(int n){
	for(int i=0;i<n;i++)memo[i]=make_pair(-1,-1);
	int k=1;
	while(k*(k+1)<n)k++;
	int sz=0;
	for(int i=0;i<=k;i++){
		pair<int,int> p=qry(i);
		sz=max(sz,p.first+p.second);
	}
	for(int start=0;start<=k;start++){
		pair<int,int> p=qry(start);
		if(p.first+p.second==sz){
			int ans=start;
			while(ans<n){
				p=qry(ans);
				if(p.first+p.second==sz){
					int l=ans,r=find(p.first+1)-1; // rightmost thing with the same p
					pair<int,int> p2;
					while(l<r){
						int mid=(l+r+1)/2;
						p2=qry(mid);
						if(p2==p){
							l=mid;
						}else{
							r=mid-1;
						}
					}
					ans=l+1;
				}else{
					if(p.first==0&&p.second==0)break;
					ans++;
				}
			}
			return ans;
		}else if(p.first==0&&p.second==0){
			return start;
		}
	}
	return n;
}
/*
8
3 2 3 1 3 3 2 3
*/

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