Submission #252682

#	Time	Username	Problem	Language	Result	Execution time	Memory
252682		ChrisT	Gap (APIO16_gap)	C++17	70 / 100	74 ms	1936 KiB

gap

#include<bits/stdc++.h>
using namespace std;
#include "gap.h"
long long findGap (int t, int n) {
	if (t == 1) {
		vector<long long> arr(n+1);
		long long low = -1, high = 1e18+1;
		for (int i = 1; i <= (n+1)/2; i++) {
			MinMax(low+1,high-1,&low,&high);
			arr[i] = low; arr[n-i+1] = high;
		}
		long long mx = 0;
		for (int i = 1; i < n; i++) {
			mx = max(mx,arr[i+1] - arr[i]);
		}
		return mx;
	} else {
		long long mx,mn;
		MinMax(0,1e18,&mn,&mx); 
		long long go = max(1LL,(mx - mn + n - 2) / (n - 1)), ret = 0, lstmx = mn;
		for (long long cur = mn+1; cur < mx; cur += go) {
			long long ed = min(cur + go-1,mx-1);
			long long low,high;
			MinMax(cur,ed,&low,&high);
			if (low != -1) {
				ret = max(ret,low - lstmx);
				lstmx = high;
			}
		}
		ret = max(ret,mx - lstmx);
		return ret;
	}
}

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