Submission #37722

#	Time	Username	Problem	Language	Result	Execution time	Memory
37722		szawinis	Gap (APIO16_gap)	C++14	100 / 100	106 ms	5800 KiB

gap

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

ll findGap(int t, int n) {
	ll ans = 0;
	if(t == 1) {
		ll l = 0, r = 1e18;
		ll a[n+1];
		for(int i = 1; i <= n+1 >> 1; i++) {
			MinMax(l, r, &l, &r);
			a[i] = l;
			a[n-i+1] = r;
			++l, --r;
		}
		for(int i = 1; i < n; i++) ans = max(a[i+1] - a[i], ans);
	} else {
		ll l = 0, r = 1e18;
		MinMax(l, r, &l, &r);
		ll blk = (r-l+n-2) / (n-1);
		assert(blk >= 1);
		ll x = l, pre = 0;
		while(x < r) {
			ll tmpl, tmpr;
			MinMax(x, x+blk-1, &tmpl, &tmpr);
			if(tmpl == -1 && tmpr == -1) {
				x += blk;
				continue;
			}
			if(x != l) ans = max(tmpl - pre, ans);
			pre = tmpr;
			x += blk;
		}
		if(x == r) ans = max(x - pre, ans);
	}
	return ans;
}

Compilation message (stderr)

gap.cpp: In function 'll findGap(int, int)':
gap.cpp:11:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   for(int i = 1; i <= n+1 >> 1; i++) {
                        ^

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