Submission #744817

#	Time	Username	Problem	Language	Result	Execution time	Memory
744817		Suvd	Gap (APIO16_gap)	C++14	100 / 100	58 ms	1872 KiB

gap

#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const long long INF = 1e18;
 
long long findGap(int T, int N){
	if(T==1){
		ll mn = 0, mx = INF;
		int l=0,r=N-1;
		vector<ll>a(N);
		while(l <= r){
			MinMax(mn,mx,&mn,&mx);
			a[l++]=mn;
			a[r--]=mx;
			mn+=1;mx-=1;
		}
		ll diff = 0;
		for(int i=1;i<N;i++){
			diff=max(diff,a[i]-a[i-1]);
		}
		return diff;
	}
	ll mn = 0, mx = INF;
	MinMax(mn,mx,&mn,&mx);
	ll min_diff = (mx - mn) / (N - 1) + 1;
	ll ans = 0, prev = -INF;
	for(ll i = mn; i <= mx; i += min_diff){
		ll l, r;
		MinMax(i,i+min_diff-1,&l,&r);
		if( l == -1 )continue;
		if( prev == -INF ) prev = l;
		ans = max(ans, l - prev);
		ans = max(ans, r - l);
		prev = r;
	}
	return ans;
}

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