Submission #117935

#	Time	Username	Problem	Language	Result	Execution time	Memory
117935		win11905	Gap (APIO16_gap)	C++11	70 / 100	64 ms	2416 KiB

gap

#include <bits/stdc++.h>
#include "gap.h"
#define long long long
using namespace std;

long MX = 1e18;

long findGap(int T, int N) {
	long mn, mx;
	if(T == 2) {
		MinMax(0, MX, &mn, &mx);
		long sz = (mx-mn+N-2) / (N-1);		
		long ans = sz;
		long pv = mn;
		long z = mx;
		long p = mn;
		while(p <= z) {
			MinMax(p, p+sz, &mn, &mx);
			if(mn != -1) {
				ans = max(ans, mn - pv);
				pv = mx;
			}
			p += sz+1;
		}
		return ans;
	} else {
		vector<long> vec;
		long l = 0, r = MX;
		while(true) {
			MinMax(l, r, &mn, &mx);
			if(mn != -1) vec.emplace_back(mn);
			if(mn != mx) vec.emplace_back(mx);
			l = mn+1, r = mx-1;
			if(mn == mx || mn == -1 || l > r) break;
		}
		sort(vec.begin(), vec.end());
		long ans = 0;
		for(int i = 1; i < N; ++i) ans = max(ans, vec[i] - vec[i-1]);
		return ans;
	}
}

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