제출 #1206221

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1206221		borisAngelov	Gap (APIO16_gap)	C++20	100 / 100	39 ms	1968 KiB

gap

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

using namespace std;

const long long inf = 1e18;

long long solve1(int n)
{
	vector<long long> v(n, 0);
	
	long long x, y;
	MinMax(0, inf, &x, &y);

	if (n == 2) return y - x;

	int ptrL = 0, ptrR = n - 1;
	v[ptrL++] = x;
	v[ptrR--] = y;

	for (int i = 1; i < (n + 1) / 2; ++i)
	{
		MinMax(x + 1, y - 1, &x, &y);
		v[ptrL++] = x;
		v[ptrR--] = y;
	}

	long long ans = 0;

	for (int i = 1; i < n; ++i)
	{
		ans = max(ans, v[i] - v[i - 1]);
	}

	return ans;
}

long long findGap(int T, int N)
{
	if (T == 1)
	{
		return solve1(N);
	}

	int n = N;
	long long a, b;
	MinMax(0, inf, &a, &b);

	if (n == 2)
	{
		return b - a;
	}

	long long step = (b - a) / (1LL * (n - 1)) + 1;
	long long last = a, ans = step - 1;

	for (long long i = a; i <= b; i += step)
	{
		long long x, y;
		MinMax(i, i + step - 1, &x, &y);

		if (x == -1) continue;

		ans = max(ans, x - last);
		last = y;
	}

	return ans;
}

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