Submission #406924

#	Time	Username	Problem	Language	Result	Execution time	Memory
406924		SeDunion	Gap (APIO16_gap)	C++17	40.31 / 100	328 ms	2740 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;

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

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: 10.3130917791 / 70