Submission #30779

#	Time	Username	Problem	Language	Result	Execution time	Memory
30779		cdemirer	Gap (APIO16_gap)	C++14	0 / 100	106 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) {
		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;
}

ll subtask2(int N) {
	return 1337;
}

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

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