Submission #61204

#	Time	Username	Problem	Language	Result	Execution time	Memory
61204		Eae02	Gap (APIO16_gap)	C++14	100 / 100	100 ms	2284 KiB

gap

#include "gap.h"

#include <bits/stdc++.h>

using ll = long long;

ll gMaxDiff = 0;

long long findGap(int T, int N)
{
	if (T == 1)
	{
		ll min = 0;
		ll max = 1000000000000000000;
		
		std::vector<ll> numbers(N);
		for (int i = 0; 2 * i < N; i++)
		{
			ll nextMin, nextMax;
			MinMax(min, max, &nextMin, &nextMax);
			
			numbers[i] = nextMin;
			numbers[numbers.size() - i - 1] = nextMax;
			
			min = nextMin + 1;
			max = nextMax - 1;
		}
		
		for (int i = 1; i < N; i++)
		{
			gMaxDiff = std::max(gMaxDiff, numbers[i] - numbers[i - 1]);
		}
	}
	else
	{
		ll min, max;
		MinMax(0, 1000000000000000000, &min, &max);
		
		if (N <= 2)
			return max - min;
		
		ll step = std::ceil((max - min) / (double)(N - 2));
		ll prev = min;
		for (ll i = min; i < max; i += step)
		{
			ll nMin, nMax;
			MinMax(i + 1, i + step, &nMin, &nMax);
			//std::cout << nMin << " " << nMax << ", " << nMin - prev << std::endl;
			
			if (nMin == -1)
				continue;
			gMaxDiff = std::max(gMaxDiff, nMin - prev);
			prev = nMax;
		}
		
		gMaxDiff = std::max(gMaxDiff, max - prev);
		
		//maxDiff(min, max);
	}
	
	return gMaxDiff;
}

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