제출 #1265455

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1265455		canhnam357	Gap (APIO16_gap)	C++20	100 / 100	46 ms	3260 KiB

gap

#include "gap.h"
#include <bits/stdc++.h>
using namespace std;

long long findGap(int T, int N)
{
	if (T == 1)
	{
		vector<long long> vl, vr;
		long long s = 0, e = 1e18, l, r;
		while (s <= e && vl.size() + vr.size() < N)
		{
			MinMax(s, e, &l, &r);
			if (l == -1) break;
			vl.push_back(l);
			if (l != r)
			vr.push_back(r);
			s = l + 1;
			e = r - 1;
		}
		reverse(vr.begin(), vr.end());
		for (long long i : vr) vl.push_back(i);
		long long ans = 0;
		assert(vl.size() == N);
		for (int i = 1; i < N; i++)
		{
			ans = max(ans, vl[i] - vl[i - 1]);
		}
		return ans;
	}
	long long l, r;	
	MinMax(0LL, (long long)1e18, &l, &r);
	if (N == 2) return r - l;
	long long left = l, right = r;
	long long d = (right - 1 - left) / (N - 2);
	vector<pair<long long, long long>> a;
	for (int i = 0; i < N - 2; i++)
	{
		a.emplace_back(left + 1 + d * i, left + d * (i + 1));
	}
	a.back().second = right - 1;
	long long ans = 0, cur = l;
	for (auto [s, e] : a)
	{
		MinMax(s, e, &l, &r);
		if (l == -1) continue;
		ans = max(ans, l - cur);
		cur = r;
	}
	ans = max(ans, right - cur);
	return ans;
}

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