제출 #545082

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
545082		Sohsoh84	Gap (APIO16_gap)	C++17	100 / 100	58 ms	2244 KiB

gap

#include <bits/stdc++.h>
#include "gap.h"

using namespace std;

typedef long long ll;

#define debug(x)		cerr << #x << ": " << x << endl;
#define sep			' '
#define all(x)			(x).begin(),(x).end()

const ll INF = 2e18;

ll findGap(int t, int n) {
	if (t == 1) {
		ll l = -1, r = INF;
		vector<ll> vec;
	
		int t = (n + 1) >> 1;
		while (t-- && l < r) {
			MinMax(l, r, &l, &r);	

			if (l != -1) {
				vec.push_back(l);
				vec.push_back(r);
			}

			l++;
			r--;	
		}	

		sort(all(vec));
		ll ans = 0;
		for (int i = 1; i < int(vec.size()); i++)
			ans = max(ans, vec[i] - vec[i - 1]);
		return ans;
	}

	ll mn = 0, mx = INF;
	MinMax(0, INF, &mn, &mx);
	if (n == 1) return 0;

	ll len = mx - mn;
	ll sq = (len + n - 2) / (n - 1), ans = sq;

	vector<ll> vec;
	for (ll l = mn; l <= mx; l += sq + 1) { // sq + 1
		ll a = 0, b = 0;
		MinMax(l, l + sq, &a, &b); //
		
		if (a >= 0) {
			if (!vec.empty()) ans = max(ans, a - vec.back());
			vec.push_back(b);
		}
	}

	return ans;
}

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