Submission #139022

#	Time	Username	Problem	Language	Result	Execution time	Memory
139022		sheyasutaka	Gap (APIO16_gap)	C11	30 / 100	69 ms	3832 KiB

gap

#include "gap.h"

long long findGap(int T, int N) {
	long long a[N + 5], ln = 0;
	long long l = 0, r = 1000000000000000000LL;
	if (T == 1) {
		int i = 0, j = N - 1;
		while (i <= j) {
			MinMax(l, r, &a[i], &a[j]);
			l = a[i] + 1;
			r = a[j] - 1;
			i++;
			j--;
		}
		ln = N;
	} else {
		MinMax(l, r, &l, &r);
		long long len = (r - l - 1) / (N - 1);
		long long ad = (r - l - 1) % (N - 1);


		a[ln++] = l;
		long long x, y;
		l++;
		for (int i = 0; i < N - 1; i++) {
			long long lx = len + ((i < ad) ? 1 : 0);
			MinMax(l, l + lx - 1, &x, &y);
			l += lx;

			if (x >= 0) {
				a[ln++] = x;
				a[ln++] = y;
			}
		}
		a[ln++] = r;
	}

	long long result = 0;
	for (int i = 1; i < ln; i++) {
		long long maybe = a[i] - a[i - 1];
		if (maybe > result) result = maybe;
	}
	return result;
}

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