Submission #406925

#	Time	Username	Problem	Language	Result	Execution time	Memory
406925		SeDunion	Gap (APIO16_gap)	C++17	30 / 100	3084 ms	263068 KiB

gap

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

ll Answer(vector<ll>a) {
	int N = a.size();
	ll answer = 0;
	for (int i = 0 ; i < N - 1 ; ++ i) answer = max(answer, a[i + 1] - a[i]);
	return answer;
}

ll solve1(int N) {
	ll L = -1, R = ll(1e18)+1;
	vector<ll>a(N);
	int l = 0, r = N - 1;
	while (l <= r) {
		MinMax(L+1, R-1, &L, &R);
		a[l++] = L, a[r--] = R;
	}
	return Answer(a);
}

vector<ll>a;

mt19937 rnd(random_device{}());

void solve(ll L, ll R) {
	if (L > R) return;
	ll M = (L + R) / 2;
	ll X;
	if (rnd() & 1) {
		MinMax(L, M, &L, &X);
		if (L != -1) a.emplace_back(L);
		if (X != -1 && L != X) a.emplace_back(X);
		if (L != -1 && X != -1) solve(L + 1, X - 1);
		solve(M + 1, R);
	} else {
		MinMax(L, M, &X, &R);
		if (R != -1) a.emplace_back(R);
		if (X != -1 && R != X) a.emplace_back(X);
		if (R != -1 && X != R) solve(X + 1, R - 1);
		solve(L, M - 1);
	}
}

ll solve2(int N) {
	ll L, R;
	MinMax(0, ll(1e18), &L, &R);
	a.emplace_back(L);
	a.emplace_back(R);
	solve(L + 1, R - 1);
	sort(a.begin(), a.end());
	assert((int)a.size() == N);
	return Answer(a);
}

ll findGap(int T, int N) {
	if (T == 1) {
		return solve1(N);
	} else {
		return solve2(N);
	}
}

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