Submission #797421

#	Time	Username	Problem	Language	Result	Execution time	Memory
797421		WongChun1234	The Big Prize (IOI17_prize)	C++14	90 / 100	77 ms	2816 KiB

prize

#include "prize.h"
#include<bits/stdc++.h>
using namespace std;
const int N=200050;
const bool DEBUG=0;
int n,l,r,lbound,rbound,mid,done[N],mx;
pair<int,int> res[N];
vector<int> pos,apos;

pair<int,int> qry(int id){
	if (id>=n||id<0) return {-1,-1};
	if (done[id]) return res[id];
	vector<int> resp=ask(id);
	done[id]=1;
	res[id]={resp[0],resp[1]};
	return res[id];
}

int sum(int id){
	return qry(id).first+qry(id).second;
}

int find_best(int N) {
	n=N;
	if (n<=5000&&(!DEBUG)){
		for (int i=0;i<n;i++){
			if (sum(i)==0) return i;
		}
	}
	for (int i=0;i<min(712,n);i++){
		mx=max(mx,sum(i));
	}
	pos.push_back(-1);
	for (int i=0;i<min(712,n);i++){
		if (sum(i)<mx) pos.push_back(i),apos.push_back(i);
	}
	pos.push_back(n);
	if (DEBUG) mx=3;
	if (DEBUG) pos={-1,6};
	if (DEBUG) for (int i:pos) cout<<i<<"!\n";
	for (int i=1;i<pos.size();i++){
		l=pos[i-1]+1,r=pos[i]-1;
		while (l<=r&&sum(l)<mx) l++;
		while (l<=r&&sum(r)<mx) r--;
		if (DEBUG) cout<<"start "<<l<<" "<<r<<"\n";
		while (qry(l).first!=qry(r).first){
			if (DEBUG) cout<<l<<"-"<<r<<"\n";
			if (r-l+1<=3){
				for (int j=l;j<=r;j++) res[j]=qry(j);
				break;
			}
			lbound=l,rbound=r-1;
			//goal: find last ==l.first
			while (lbound<rbound){
				mid=(lbound+rbound)/2;
				while (sum(mid)<mx) mid--;
				if (mid==lbound) break;
				if (qry(mid).first==qry(l).first) lbound=mid;
				else rbound=mid-1;
			}
			if (DEBUG) cout<<"found "<<lbound+1<<"\n";
			assert(sum(lbound+1)<mx);
			l=lbound+2;
			while (l<=r&&sum(l)<mx) l++;
			while (l<=r&&sum(r)<mx) r--;
		}
	}
	for (int i=0;i<n;i++){
		if (done[i]&&sum(i)==0) return i;
	}
	return -1;
}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:41:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |  for (int i=1;i<pos.size();i++){
      |               ~^~~~~~~~~~~

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