Submission #545067

#	Time	Username	Problem	Language	Result	Execution time	Memory
545067		Sohsoh84	Gap (APIO16_gap)	C++17	0 / 100	55 ms	2276 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 - 1) / (n - 1), ans = sq;

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

	for (int i = 1; i < int(vec.size()); i++) {
		ans = max(ans, vec[i] - vec[i - 1]);
	}

	return ans;
}

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