Submission #314095

#	Time	Username	Problem	Language	Result	Execution time	Memory
314095		keta_tsimakuridze	The Big Prize (IOI17_prize)	C++14	96.17 / 100	63 ms	2808 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],P[200005];
int find_best(int n) {
	int f=474;
	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;
			P[i]={1,{res[0],res[1]}};
		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;
		res.resize(2);
			if(!P[i].f)res= ask(i),P[i]={1,{res[0],res[1]}};
			else res[0]=P[i].s.f,res[1]=P[i].s.s;
		R++;
		b[R]={res[0]+res[1],{res[0],i}};
		P[i]={1,{res[0],res[1]}};
		if(res[0]+res[1]==0) return i;
	}
	if(R*f!=n-1){ 
	R++;
	std::vector<int> res;
	res.resize(2);
			if(!P[n-1].f)res= ask(n-1),P[n-1]={1,{res[0],res[1]}};
			else res[0]=P[n-1].s.f,res[1]=P[n-1].s.s;
	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;
		 if(ind+1>l) l=ind+1;
		 r=b[idx].s.s;
		while(l<=r){
			int mid=(l+r)/2;
			std::vector<int> res;
			res.resize(2);
			if(!P[mid].f)res= ask(mid),P[mid]={1,{res[0],res[1]}};
			else res[0]=P[mid].s.f,res[1]=P[mid].s.s;
			
			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;
			res.resize(2);
			if(!P[idx].f) res= ask(idx);
			else res[0]=P[idx].s.f,res[1]=P[idx].s.s;
			if(res[0]+res[1]==mx){
			 ind=idx;le=res[0];break;}
			if(res[0]+res[1]==0) return idx;
		}
	}
	return 0;
}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:12:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   12 |   if(res[0] + res[1] == 0)
      |   ^~
prize.cpp:14:4: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   14 |    P[i]={1,{res[0],res[1]}};
      |    ^

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