Submission #111568

#	Time	Username	Problem	Language	Result	Execution time	Memory
111568		aleksam	Gap (APIO16_gap)	C++14	71.01 / 100	85 ms	1924 KiB

gap

#include "gap.h"
#include <bits/stdc++.h>
#define LLMAX 1000000000000000000LL

long long findGap1(int N){
	long long mn, mx;
	long long a[N];
	MinMax(1, LLMAX, &mn, &mx);
	a[0]=mn;
	a[N-1]=mx;
	for(int i=1; i<=N-1-i; ++i){
		MinMax(a[i-1]+1, a[N-i]-1, &mn, &mx);
		a[i]=mn;
		a[N-i-1]=mx;
	}
	
	long long maxdiff=1;
	for(int i=0; i<N-1; ++i){
		if(a[i+1]-a[i]>maxdiff)
			maxdiff=a[i+1]-a[i];
	}
	return maxdiff;
}

long long findGap2(int N)
{
	if(N<=10)return findGap1(N);
	
	long long apsmin, apsmax;
	long long g=1, gg=1;
	while(1){
		long long mn, mx;
		MinMax(1, g+1, &mn, &mx);
		if(mn!=-1){
			apsmin=mn;
			break;
		}
		if(N>50)g*=20;
		else g*=40;
	}
	long long last=apsmin;
	while(1){
		long long mn, mx;
		bool kraj=false;
		if(last+g<LLMAX)
			MinMax(last+1, last+g, &mn, &mx);
		else {
			MinMax(last+1, LLMAX, &mn,&mx);
			kraj=true;
		}
		if(mn==-1){
			g=2*g+1;
			if(!kraj)
				continue;
			else break;
		}
		if(mn-last>gg){
			gg=mn-last;
			g=gg;
		}
		last=mx;
		if(kraj)break;
	}
	return gg;
}
long long findGap(int T, int N){
	if(T==1)return findGap1(N);
	return findGap2(N);
}
/*
1 4
2 3 6 8

1 3
1 1000000000000 1000000000000000000
*/

Compilation message (stderr)

gap.cpp: In function 'long long int findGap2(int)':
gap.cpp:29:20: warning: unused variable 'apsmax' [-Wunused-variable]
  long long apsmin, apsmax;
                    ^~~~~~

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