제출 #30806

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
30806		cdemirer	Gap (APIO16_gap)	C++14	30 / 100	2000 ms	14468 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;
	ll q, w;
	MinMax(l, r, &q, &w);
	if (q == -1) return;
	S.insert(q); S.insert(w);
	if (q == w) return;
	int mid = (q+w)/2;
	if (q+1 != mid) func(q+1, mid);
	if (mid+1 != w-1) func(mid+1, 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