Submission #96322

#	Time	Username	Problem	Language	Result	Execution time	Memory
96322		jamielim	Gap (APIO16_gap)	C++14	100 / 100	83 ms	2680 KiB

gap

#include <bits/stdc++.h>
#include "gap.h"
using namespace std;
 
long long findGap(int T,int N){
	if(T==1){
		long long arr[N];
		int a=0,b=N-1;
		long long s=0,t=1000000000000000000;
		long long mn,mx;
		while(a<=b){
			MinMax(s,t,&mn,&mx);
			arr[a]=mn;
			arr[b]=mx;
			s=mn+1;
			t=mx-1;
			a++; b--;
		}
		long long ans=0;
		for(int i=1;i<N;i++){
			ans=max(ans,arr[i]-arr[i-1]);
		}
		return ans;
	}else{
		long long s=0,t=1000000000000000000;
		long long mn,mx;
		MinMax(s,t,&mn,&mx);
		if(N==2)return mx-mn;
		long long k=mx-mn+1;
		s=mn+1;
		long long prev=mn,ans=0;
		for(int i=0;i<N-1;i++){
			t=s+(k/(N-1));
			MinMax(s,t,&mn,&mx);
			if(mn!=-1){
				ans=max(ans,mn-prev);
				prev=mx;
			}
			s=t+1;
		}
		return ans;
	}
}

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