Submission #1011661

#	Time	Username	Problem	Language	Result	Execution time	Memory
1011661		ezzzay	Gap (APIO16_gap)	C++14	100 / 100	44 ms	5008 KiB

gap

#include "gap.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const int MN=2e6;
ll arr[MN];
long long findGap(int T, int N){
	if(T==1){
int l=0,r=N-1;
	ll s=0,t=1e18;
	while(1){
		ll mn,mx;
		MinMax(s,t,&mn,&mx);
		arr[l]=mn;
		arr[r]=mx;
		s=mn+1;
		t=mx-1;

		if(l+1==r or l==r)break;
		l++;
		r--;
		
	}
	ll ans=0;
	for(int i=1;i<N;i++){
		ans=max(ans,arr[i]-arr[i-1]);
	}
	return ans;
	}
	else{
		ll mn,mx;
		MinMax(0,1e18,&mn,&mx);
		ll k=(mx-mn+N-2)/(N-1);
		ll ans=k,x,y,l=mn,i;
		for(i=mn;i<mx-k;i+=k+1){
			MinMax(i,i+k,&x,&y);
			if(x!=-1){
				ans=max(ans,x-l);
				l=y;
			}
		}
		MinMax(i,mx,&x,&y);
		if(x!=-1)ans=max(ans,x-l);
		return ans;

	}
	return 1;
	
}

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