Submission #1164916

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164916		KickingKun	Gap (APIO16_gap)	C++20	89.02 / 100	38 ms	2668 KiB

gap

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

#define ll long long

ll findGap(int T, int N) {
	if (T == 1 || N <= 4) {
		vector <ll> A, B;
		ll l = 0, r = 1e18;
		while (l <= r && A.size() + B.size() < N) {
			ll x, y; MinMax(l, r, &x, &y);
			if (x == -1) break;
			A.emplace_back(x);
			if (x < y) B.emplace_back(y);
			l = x + 1, r = y - 1;
		}
		for (int i = B.size() - 1; i > -1; i--)
			A.emplace_back(B[i]);
		
		ll ans = 0;
		for (int i = 1; i < A.size(); i++)
			ans = max(ans, A[i] - A[i - 1]);
		return ans;
	}
	
	else {		
		ll l, r; MinMax(0, 1e18, &l, &r);
		ll blockSize = (r - l) / (N - 1) + ((r - l) % (N - 1) != 0);
		ll ans = blockSize;
		for (ll i = l, pre = -1; i <= r; i += blockSize) {
			ll x = i, y = i + blockSize - 1, a, b;
			MinMax(x, y, &a, &b);
			if (a != -1) {
				if (pre != -1) ans = max(ans, a - pre);
				pre = b;
			}
		}
		return ans;
	}
}

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