Submission #30810

#	Time	Username	Problem	Language	Result	Execution time	Memory
30810		cdemirer	Gap (APIO16_gap)	C++14	30 / 100	2000 ms	9900 KiB

gap

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> llp;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<vii> vvii;
#define pb(x) push_back(x)
#define mp(x, y) make_pair(x, y)
#include "gap.h"

set<ll> S;

ll subtask1(int N) {
	//cerr << N << endl;
	ll l = 0, r = 1e18+1;
	ll q, w;
	while (N > 0) {
		MinMax(l, r, &q, &w);
		//cerr << q << w << endl;
		S.insert(q); S.insert(w);
		l = q+1;
		r = w-1;
		N -= 2;
	}
	set<ll>::iterator it = S.begin();
	it++;
	ll best = 0;
	for (; it != S.end(); it++) {
		set<ll>::iterator it2 = it;
		it2--;
		best = max(best, (*it) - (*it2));
	}
	return best;
}

void func(ll l, ll r) {
	if (l > r) return;
	if (l <= 0 || r <= 0) return;
	ll q, w;
	MinMax(l, r, &q, &w);
	if (q == -1) return;
	S.insert(q); S.insert(w);
	if (q == w) return;
	if (q == w-1) return;
	if (q == w-2) {
		func(q+1, q+1);
		return;
	}
	ll mid = (q+w)/2;
	func(q+1, mid);
	func(mid, w-1);
}

ll subtask2(int N) {
	func(0, 1e18);
	set<ll>::iterator it = S.begin();

	/*set<ll>::iterator dbgit = it;
	while (dbgit != S.end()) {
		cerr << *dbgit << endl;
		dbgit++;
	}*/


	it++;
	ll best = 0;
	for (; it != S.end(); it++) {
		set<ll>::iterator it2 = it;
		it2--;
		best = max(best, (*it) - (*it2));
	}
	return best;
}

long long findGap(int T, int N)
{
	if (T == 1) return subtask1(N);
	else return subtask2(N);
}

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