Submission #388957

#	Time	Username	Problem	Language	Result	Execution time	Memory
388957		mosiashvililuka	Gap (APIO16_gap)	C++14	100 / 100	72 ms	1900 KiB

gap

#include "gap.h"
#include<bits/stdc++.h>
using namespace std;
const long long K=1000000000000000000LL;
long long a,b,c,d,e,i,j,ii,jj,zx,xc,lef,rig,mid,f[100009],x,pas;
int B,C,D,E;
long long findGap(int T, int NN)
{
	a=NN;
	if(T==1){
		lef=0;rig=K;
		zx=0;
		while(1){
			if(zx*2>=a) break;
			MinMax(lef,rig,&c,&d);
			if(c==-1){
				break;
			}
			if(c==d){
				zx++;
				f[zx]=c;
				break;
			}
			zx++;
			f[zx]=c;f[a-zx+1]=d;
			lef=c+1;rig=d-1;
		}
		e=0;
		for(i=1; i<a; i++){
			e=max(e,f[i+1]-f[i]);
		}
		return e;
	}else{
		MinMax(0,K,&f[1],&f[a]);
		if(a==2){
			return f[a]-f[1];
		}
		x=(f[a]-f[1])/(a-1);
		if((f[a]-f[1])%(a-1)!=0) x++;
		lef=f[1]+1;
		zx=f[1];
		pas=0;
		while(1){
			if(lef>=f[a]) break;
			rig=min(f[a]-1,lef+x-1);
			MinMax(lef,rig,&c,&d);
			if(c!=-1){
				pas=max(pas,c-zx);
				zx=d;
			}
			lef=rig+1;
		}
		pas=max(pas,f[a]-zx);
		return pas;
	}
	return 0;
}

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