Submission #165257

#	Time	Username	Problem	Language	Result	Execution time	Memory
165257		Segtree	The Big Prize (IOI17_prize)	C++14	90 / 100	119 ms	508 KiB

prize

#include<iostream>
#include"prize.h"
using namespace std;
typedef long long ll;

int find_best(int n){
    vector<int> a,b,v;
    int bef=-1;
    int ma=-1;
    for(int i=0;i<min(n,600);i++){
	a=ask(i);
	int t=a[0]+a[1];
	if(t==0)return i;
	if(t>ma){
	    ma=t;
	}
    }//
    for(int i=0;i<min(n,600);i++){
	a=ask(i);
	int t=a[0]+a[1];
	if(t!=ma){
	    bef=i;
	    break;
	}
    }//はじめての上が見つかるorすべてアメ
    
    
    while(1){
	b=ask(bef+1); if(b[0]+b[1]==0)return bef+1;
	if(b[0]+b[1]!=ma){
	    bef=bef+1;
	    continue;
	}
	ll l=bef+1,r=n-1,mid;
	while(l<r-1){
	    mid=(l+r)>>1;
	    a=ask(mid);
	    if(a[0]+a[1]==ma){
		if(a==b)l=mid;
		else r=mid;
	    }
	    else{
		r=mid;
	    }
	}
	bef=r;
	b=ask(r); if(b[0]+b[1]==0)return r;
    }
}

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