Submission #545070

#	Time	Username	Problem	Language	Result	Execution time	Memory
545070		Sohsoh84	Gap (APIO16_gap)	C++17	53.51 / 100	63 ms	2240 KiB

gap

#include <bits/stdc++.h>
#include "gap.h"

using namespace std;

typedef long long ll;

#define debug(x)		cerr << #x << ": " << x << endl;
#define sep			' '

const ll INF = 2e18;

ll findGap(int t, int n) {	
	ll mn = 0, mx = INF;
	MinMax(0, INF, &mn, &mx);
	if (n == 1) return 0;

	ll len = mx - mn;
	ll sq = (len + n - 2) / (n - 1), ans = sq;

	vector<ll> vec;
	for (ll l = mn; l <= mx; l += sq) { // sq + 1
		ll a = 0, b = 0;
		MinMax(l, l + sq - 1, &a, &b); //
		
		if (a >= 0) {
			if (!vec.empty()) ans = max(ans, a - vec.back());
			vec.push_back(b);
		}
	}

	return ans;
}

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