Submission #933381

#	Time	Username	Problem	Language	Result	Execution time	Memory
933381		SmuggingSpun	Gap (APIO16_gap)	C++14	30 / 100	53 ms	3628 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){
	ll ans = 0;
	if(T == 1){
		vector<ll>a(n);
		ll 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]);
		}
	}
	else{
		ll a_1, a_n;
		MinMax(0, 1e18, &a_1, &a_n);
		ll average = (a_n - a_1 + n - 2) / (n - 1);
		while(true){
			ll next_value = -1, temp, to = a_1;
			while((to += average) < a_n && next_value == -1){
				MinMax(a_1 + 1, to, &next_value, &temp);
			}
			maximize(ans, (next_value == -1 ? a_n : next_value) - a_1);
			a_1 = temp;
			if(next_value == -1){
				break;
			}
		}
	} 
	return ans;
}

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