제출 #287257

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
287257		mosiashvililuka	커다란 상품 (IOI17_prize)	C++14	20 / 100	97 ms	2036 KiB

prize

#include<bits/stdc++.h>
#include "prize.h"
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,sq,lef,rig,mid,pas,mx,lf[200009],rg[200009];
int find_best(int n) {
	vector <int> ans,lp;
	lp.resize(2);
	a=n;
	int sq=sqrt(a);
	for(i=1; i<=sq+1; i++){
		ans=ask(i-1);
		if(ans[0]+ans[1]==0){
			return i-1;
		}
		lf[i]=ans[0];
		rg[i]=ans[1];
		mx=max(ans[0]+ans[1],mx);
	}
	for(i=1; ; i++){
		if(lf[i]+rg[i]==mx) break;
	}
	while(1){
		lef=i;rig=a+1;
		lp[0]=lf[i];lp[1]=rg[i];
		pas=0;
		while(1){
			if(lef+1>=rig) break;
			mid=(lef+rig)/2;
			ans=ask(mid-1);
			lf[mid]=ans[0];rg[mid]=ans[1];
			if(ans[0]==0&&ans[1]==0){
				return mid-1;
			}
			if(ans[0]==lp[0]&&ans[1]==lp[1]){
				lef=mid;
			}else{
				rig=mid;
				pas=mid;
			}
		}
		i=pas;
		for(i=i+1; ; i++){
			ans=ask(i-1);
			lf[i]=ans[0];rg[i]=ans[1];
			if(ans[0]+ans[1]==0){
				return i-1;
			}
			if(ans[0]+ans[1]==mx){
				break;
			}
		}
	}
}

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