Submission #1050590

#	Time	Username	Problem	Language	Result	Execution time	Memory
1050590		matere	Gap (APIO16_gap)	C++14	30 / 100	38 ms	2680 KiB

gap

#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
long long findGap(int T, int N){
	if(T==1){
		long long mn=-1,mx=-1;
		MinMax(1,1000000000000000000,&mn,&mx);
		long long premn=mn,premx=mx;
		long long ans=0;
		for(int i=1;i<(N+1)/2;i++){
			premn=mn,premx=mx;
			MinMax(mn+1,mx-1,&mn,&mx);
			ans=max(ans,mn-premn);
			ans=max(ans,premx-mx);
		}
		ans=max(ans,mx-mn);
		return ans;
	}
	long long mn=-1,mx=-1;
	MinMax(1,1000000000000000000,&mn,&mx);
	long long diff = mx-mn;
	long long mxx = mx;
	long long mnd=diff/(N-1);
	long long ans=mnd,curm=mn;
	for(long long i=mn+1;i<=mxx-1;i+=mnd){
		// cout<<i<<' '<<i+mnd-1<<' ';
		MinMax(i,min(mxx-1,i+mnd-1),&mn,&mx);
		// cout<<mn<<' '<<mx<<endl;
		if(mn==-1) continue;
		// cout<<mn<<' '<<curm<<endl;
		ans=max(ans,mn-curm);
		curm=mx;
	}
	return ans;
}

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