Submission #24674

#	Time	Username	Problem	Language	Result	Execution time	Memory
24674		chan492811	Gap (APIO16_gap)	C++11	100 / 100	79 ms	4240 KiB

gap

#include "gap.h"
#include <cstdio>
#include <algorithm>
#define ll long long
#define MAX_V (ll)1e18
using namespace std;

ll res;

long long findGap(int t, int n){
	int i;
	ll l, r, nl, nr, now, tmp;
	MinMax(0ll, MAX_V, &l, &r);
	if(t == 1){
		n -= 2;
		while(n > 0){
			MinMax(l + 1, r - 1, &nl, &nr);
			res = max(res, max(r - nr, nl - l));
			l = nl; r = nr;
			n -= 2;
		}
		res = max(res, r - l);
		return res;
	}
	res = now = (r - l + (n - 2)) / (n - 1); nl = l;
	for(i = 1; i < n; i++){
		MinMax(l + now * (i - 1) + i, l + now * i + i, &nr, &tmp);
		res = max(res, nr - nl);
		if(tmp != -1) nl = tmp;
	}
	return res;
}

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