Submission #1193719

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193719		tkm_algorithms	Gap (APIO16_gap)	C++20	100 / 100	39 ms	1864 KiB

gap

/**
*    In the name of Allah
*    We are nothing and you're everything
**/
#include <bits/stdc++.h>
#include "gap.h"

using namespace std;
using ll = long long;

#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()

const ll inf = 1e18;

ll findGap(int t, int n) {
	if (t == 1) {
		ll l = 0, r = inf;
		vector<ll> a(n);
		for (int i = 0; i < (n+1)>>1; ++i) {
			ll mn, mx;
			MinMax(l, r, &mn, &mx);
			a[i] = mn;
			a[n-i-1] = mx;
			l = mn+1, r = mx-1;
		}
		
		ll ans = 0;
		for (int i = 0; i < n-1; ++i)ans = max(ans, a[i+1]-a[i]);
		
		return ans;
	}
	if (t == 2) {
		ll l = 0, r = inf, mn, mx;
		MinMax(l, r, &mn, &mx);
		
		ll ans = (mx-mn)/(n-1), last = mn;

		l = mn+1, r = mx;		
		while (l < r) {
			MinMax(l, l+ans-1, &mn, &mx);
			l += ans, ans = max(ans, mn-last);
			if (mx != -1)last = mx;
		}
		ans = max(ans, r-last);
		return ans;
	}
}

Compilation message (stderr)

gap.cpp: In function 'll findGap(int, int)':
gap.cpp:48:1: warning: control reaches end of non-void function [-Wreturn-type]
   48 | }
      | ^

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