Submission #838579

#	Time	Username	Problem	Language	Result	Execution time	Memory
838579		tch1cherin	Gap (APIO16_gap)	C++17	40.55 / 100	928 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 Minl = -1, Maxl = -1, Minr = -1, Maxr = -1;
			int children = max(2, min((N + 1) / 2 + 1, (int)sqrt(N) / 2));
			for (int i = 0; i < children; i++) {
				long long start = min(r, (long long)floorl(l + (r - l + 1) * ((1.0l / children) * i)));
				long long end = min(r, (long long)floorl(l + (r - l + 1) * ((1.0l / children) * (i + 1))) - 1);
				if (start > end) {
					continue;
				}
				MinMax(start, end, &Minr, &Maxr);
				if (Minr != -1) {
					if (Maxl != -1) { 
						maxConfirmed = max(maxConfirmed, Minr - Maxl);
					}
					Minl = Minr;
					Maxl = Maxr;
					Q.push({Minr, Maxr});
				}
			}
		}
		return maxConfirmed;
	}
}

Compilation message (stderr)

gap.cpp: In function 'long long int findGap(int, int)':
gap.cpp:43:14: warning: variable 'Minl' set but not used [-Wunused-but-set-variable]
   43 |    long long Minl = -1, Maxl = -1, Minr = -1, Maxr = -1;
      |              ^~~~

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