Submission #314015

#	Time	Username	Problem	Language	Result	Execution time	Memory
314015		keta_tsimakuridze	커다란 상품 (IOI17_prize)	C++14	20 / 100	79 ms	504 KiB

prize

#include "prize.h"
#define f first
#define s second
#include<bits/stdc++.h>
int l,r,mid,mx,ind,le,idx,R;
std::pair<int,std::pair<int,int> > b[200005];
int find_best(int n) {
	int f=500;
	if(f>n) f=n;
	for(int i = 0; i <f; i++) {
		std::vector<int> res = ask(i);
		if(res[0] + res[1] == 0)
			return i;
		if(mx<=res[0]+res[1]) mx=res[0]+res[1],ind=i,le=res[0];
	}
	f=sqrt(n);
	for(int i=f;i<n;i+=f){
		std::vector<int> res = ask(i);
		R++;
		b[R]={res[0]+res[1],{res[0],i}};
		if(res[0]+res[1]==0) return i;
	}
	if(R*f!=n-1){ 
	R++;
	std::vector<int> res = ask(n-1);
	b[R]={res[0]+res[1],{res[0],n-1}};
	if(res[0]+res[1]==0) return (n-1);
	}
	while(true){
		int l=ind/f+1;
		int r=R;
		while(l<=r){
			int mid=(l+r)/2;
			if(b[mid].f==mx && b[mid].s.f==le){
				l=mid+1;
			}
			else {
				idx=mid;
				r=mid-1;
			}
		}
		 l=b[idx-1].s.s;
		 r=b[idx].s.s;
		while(l<=r){
			int mid=(l+r)/2;
			std::vector<int> res= ask(mid);
			if(res[0]+res[1]==0) return mid;
			if(res[0]+res[1]==mx && le==res[0]) {
			l=mid+1;
			}else{
				if(res[0]+res[1]!=mx)idx=mid;
				r=mid-1;
			}
		}
		while(true){
			idx++;
			std::vector<int> res= ask(idx);
			if(res[0]+res[1]==mx){
			 ind=idx;le=res[0];break;}
			if(res[0]+res[1]==0) return idx;
		}
	}
	return 0;
}

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