제출 #1279038

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1279038		IBory	Gap (APIO16_gap)	C++20	100 / 100	43 ms	3320 KiB

gap

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

ll findGap(int T, int N) {
	vector<ll> A;
	if (T == 1) {
		ll l = 0, r = 1e18;
		for (int i = 0; i < (N + 1) / 2; ++i) {
			MinMax(l, r, &l, &r);
			A.push_back(l); A.push_back(r);
			l++; r--;
		}
	}
	else {
		ll l = 0, r = 1e18;
		MinMax(l, r, &l, &r);
		A.push_back(l); A.push_back(r);
		if (N != 2) {
			ll t = (r - l + N - 2) / (N - 1);
			for (ll i = 0; i < N - 1; ++i) {
				ll tl = l + t * i, tr = l + t * (i + 1) - 1;
				ll a, b;
				MinMax(tl, tr, &a, &b);
				if (a != -1) {
					A.push_back(a);
					A.push_back(b);
				}
			}
		}
	}

	ll ret = 0;
	sort(A.begin(), A.end());
	for (int i = 1; i < A.size(); ++i) ret = max(ret, A[i] - A[i - 1]);
	return ret;
}

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