Submission #1076893

#	Time	Username	Problem	Language	Result	Execution time	Memory
1076893		TFF	Gap (APIO16_gap)	C++17	100 / 100	45 ms	3168 KiB

gap

#include <bits/stdc++.h>
#include "gap.h"
using namespace std;
const long long MX = 1000000000000000000;
long long mn, mx;
int n;
long long findGap(int t, int N) {
	n = N;
    if (t == 1) {
		long long left, right;
		left = 0;
		right = MX;
		vector<long long> arr1, arr2;
		for (int i = 0; i < (n + 1) / 2; i++) {
			MinMax(left, right, &mn, &mx);
			arr1.push_back(mn);
			arr2.push_back(mx);
			left = mn + 1;
			right = mx - 1;
		}
		long long ans = arr2.back() - arr1.back();
		for (int i = 0; i < (int)arr1.size() - 1; i++) {
			ans = max(ans, arr1[i + 1] - arr1[i]);
			ans = max(ans, arr2[i] - arr2[i + 1]);
		}
		return ans;
	}
	MinMax(0, MX, &mn, &mx);
	long long left = mn;
	long long right = mx;
	long long delta = (mx - mn + n - 2) / (n - 1);
	vector<long long> pos;
	pos.push_back(left);
	for (int i = 0; i < n - 1; i++) {
		MinMax(min(left + i * delta + 1, right), min(left + (i + 1) * delta, right), &mn, &mx);
		if (mn != -1) {
			pos.push_back(mn);
			pos.push_back(mx);
		}
		if (left + (i + 1) * delta >= right) break;
	}
	pos.push_back(right);
	long long ans = 0;
	for (int i = 0; i < (int)pos.size(); i++) {
		ans = max(ans, pos[i + 1] - pos[i]);
	}
	return ans;
}

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