Submission #933384

#	Time	Username	Problem	Language	Result	Execution time	Memory
933384		SmuggingSpun	Gap (APIO16_gap)	C++14	30 / 100	33 ms	3760 KiB

gap

#include "gap.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>void maximize(T& a, T b){
	if(a < b){
		a = b;
	}
}
long long findGap(int T, int n){
	if(T == 1){
		vector<ll>a(n);
		ll ans = 0, low = 0, high = 1e18;
		int l = 0, r = n - 1;
		while(l <= r){
			MinMax(low, high, &a[l], &a[r]);
			low = a[l++] + 1;
			high = a[r--] - 1;
		}
		for(int i = 1; i < n; i++){
			maximize(ans, a[i] - a[i - 1]);
		}
		return ans;
	}
	ll a_1, a_n;
	MinMax(0, 1e18, &a_1, &a_n);
	ll average = (a_n - a_1 + n - 2) / (n - 1), ans = average;
	for(ll i = a_1; i <= a_n; i += average + 1){
		ll x, y;
		MinMax(i, min(i + average, a_1), &x, &y);
		if(x != -1){
			maximize(ans, x - a_1);
			a_1 = y;
		}
	}
	return ans;
}

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