Submission #1030572

#	Time	Username	Problem	Language	Result	Execution time	Memory
1030572		vjudge1	The Big Prize (IOI17_prize)	C++17	90 / 100	71 ms	11404 KiB

prize

#include "prize.h"
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define rng(i,l,r) for(int i=(l); i<(r); i++)
#define all(x) x.begin(),x.end()
using ll=long long;
const int INF=INT_MAX>>1;

vector<vector<int>> answers(200010,{-1,-1});
int ret=-1;
vector<int> query(int n){
	if(answers[n][0]!=-1)return answers[n];
	vector<int> now=ask(n);
	if(now[0]+now[1]==0)ret=n;
	answers[n]=now;
	return now;
}

int find_best(int n) {
	int MAX_OTHERS=min(n-1,500);
	int candy=0;
	rep(i,MAX_OTHERS+1){
		vector<int> now=query(i);
		candy=max(candy,now[0]+now[1]);
	}
	int pos=MAX_OTHERS+1;
	while(pos<n){
		vector<int> now=query(pos);
		if(now[0]+now[1]!=candy){
			pos++;
			continue;
		}
		int ok=pos,ng=n;
		while(ng-ok>1){
			int mid=(ok+ng)>>1;
			vector<int> mnow=query(mid);
			if(mnow[0]+mnow[1]==candy&&mnow[0]==now[0]){
				ok=mid;
			}
			else{
				ng=mid;
			}
		}
		pos=ok+1;
	}
	return ret;
}

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