Submission #1092503

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092503		alexander707070	Gap (APIO16_gap)	C++14	100 / 100	44 ms	7248 KiB

gap

#include<bits/stdc++.h>
#include "gap.h"

#define MAXN 600007
using namespace std;

const long long inf=1e18;

long long *l,*r,*ll,*rr;
long long d,ans;

vector<long long> v;

long long findGap(int T, int N){

	l=new long long();
	r=new long long();

    MinMax(1, inf, l,r);

	if(T==1){
		v.clear();

		v.push_back(*l);
		v.push_back(*r);

		for(int i=1;i<=N/2-(1-N%2);i++){
			ll=new long long();
			rr=new long long();

			if(*l+1>*r-1)break;

			MinMax((*l)+1,(*r)-1,ll,rr);

			if((*ll)==-1)break;

			v.push_back(*ll);
			v.push_back(*rr);

			l=ll; r=rr;

			if(*l==*r)break;
		}
		sort(v.begin(),v.end());

		ans=1;
		for(int i=0;i<v.size()-1;i++){
			ans=max(ans,v[i+1]-v[i]);
		}

		return ans;
	}

	d=ans=(long long) (*r-*l)/(N-1);

	while(*l!=*r){
		while(true){
			ll=new long long();
			rr=new long long();
			MinMax((*l)+1,(*l)+d+1,ll,rr);

			if((*ll)!=-1)break;

			d*=2;
		}

		ans=max(ans,*ll-*l);
		d=ans;

		l=rr;
	}

	return ans;
}

Compilation message (stderr)

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

• Subtask 1: 30 / 30
• Subtask 2: 70 / 70