Submission #793224

#	Time	Username	Problem	Language	Result	Execution time	Memory
793224		kingfran1907	Gap (APIO16_gap)	C++14	89.04 / 100	49 ms	1068 KiB

gap

#include "gap.h"
#include <algorithm>
typedef long long llint;

const llint maxn = 2e18;
using namespace std;

long long findGap(int t, int n) {
	llint sol = 0;
	if (t == 1) {
		llint a, b;
		MinMax(0, maxn, &a, &b);	
		
		while (n >= 2) {
			if (n == 2) {sol = max(sol, b - a); break;}
			n -= 2;
			llint ta, tb;
			MinMax(a + 1, b - 1, &ta, &tb);
			sol = max(sol, max(ta - a, b - tb));
			a = ta, b = tb;
		}
	} else {
		llint a, b;
		MinMax(0, maxn, &a, &b);
		
		llint delta = b - a;
		llint mini = delta / n;
		
		llint las = a;
		for (llint t = a + 1; t < b; t += mini) {
			llint ta, tb;
			if (t + mini >= b) {
				if (t >= b - 1) break;
				MinMax(t, b - 1, &ta, &tb);
			} else MinMax(t, t + mini - 1, &ta, &tb);
			
			if (ta > -1) {
				sol = max(sol, ta - las);
				las = tb;
			}
		}
		sol = max(sol, b - las);
	}
	return sol;
}

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