Submission #838548

#	Time	Username	Problem	Language	Result	Execution time	Memory
838548		tch1cherin	Gap (APIO16_gap)	C++17	44.83 / 100	79 ms	3060 KiB

gap

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

long long findGap(int T, int N) {
	if (T == 1) {
		long long Min = -1, Max = 1e18l + 1;
		vector<long long> front, back;
		for (int i = 0; i < (N + 1) / 2; i++) {
			MinMax(Min + 1, Max - 1, &Min, &Max);
			if (Min != Max) {
				front.push_back(Min);
			}
			back.push_back(Max);
		}
		reverse(back.begin(), back.end());
		vector<long long> A;
		for (auto v : front) {
			A.push_back(v);
		}
		for (auto v : back) {
			A.push_back(v);
		}
		long long gap = 0;
		for (int i = 0; i < N - 1; i++) {
			gap = max(gap, A[i + 1] - A[i]);
		}
		return gap;
	} else {
		long long Min, Max;
		MinMax(0, 1e18, &Min, &Max);
		queue<pair<long long, long long>> Q;
		Q.push({Min, Max});
		long long maxConfirmed = (Max - Min + N - 2) / (N - 1);
		uniform_real_distribution<long double> dist(0, 1);
		mt19937 rng(chrono::steady_clock().now().time_since_epoch().count());
		while (!Q.empty()) {
			auto [l, r] = Q.front();
			Q.pop();
			if (r - l <= maxConfirmed) {
				continue;
			}
			long long mid;
			if (r - l <= 32) {
				mid = (l + r) / 2;
			} else {
				mid = l + (r - l) * dist(rng);
			}
			long long Minl = -1, Maxl = -1, Minr = -1, Maxr = -1;
			if (l <= mid) {
				MinMax(l, mid, &Minl, &Maxl);
				if (Minl != -1) {
					Q.push({Minl, Maxl});
				}
			}
			if (mid + 1 <= r) {
				MinMax(mid + 1, r, &Minr, &Maxr);
				if (Minr != -1) { 
					Q.push({Minr, Maxr});
				}
			}
			if (Maxl != -1 && Minr != -1) {
				maxConfirmed = max(maxConfirmed, Minr - Maxl);
			}
		}
		return maxConfirmed;
	}
}

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