Submission #61202

#	Time	Username	Problem	Language	Result	Execution time	Memory
61202		Eae02	Gap (APIO16_gap)	C++14	30 / 100	115 ms	2300 KiB

gap

#include "gap.h"

#include <bits/stdc++.h>

using ll = long long;

ll gMaxDiff = 0;

std::set<ll> found;
int targetCount;

bool checkDone(ll min, ll max)
{
	found.insert(min);
	found.insert(max);
	if (found.size() >= targetCount)
	{
		gMaxDiff = std::max(gMaxDiff, max - min);
		return true;
	}
	return false;
}

void maxDiff(ll min, ll max)
{
	if (checkDone(min, max))
		return;
	if (max == min + 1)
	{
		gMaxDiff = std::max(gMaxDiff, max - min);
		return;
	}
	
	ll mid = min + (max - min) / 2;
	
	ll s1Min, s1Max;
	MinMax(min + 1, mid - 1, &s1Min, &s1Max);
	bool s1Pop = s1Min != -1;
	
	ll s2Min, s2Max;
	MinMax(mid, max - 1, &s2Min, &s2Max);
	bool s2Pop = s2Min != -1;
	
	if (s1Pop && s2Pop)
	{
		gMaxDiff = std::max(gMaxDiff, s2Min - s1Max);
		gMaxDiff = std::max(gMaxDiff, s1Min - min);
		gMaxDiff = std::max(gMaxDiff, max - s2Max);
	}
	else if (!s1Pop && s2Pop)
	{
		gMaxDiff = std::max(gMaxDiff, s2Min - min);
		gMaxDiff = std::max(gMaxDiff, max - s2Max);
	}
	else if (s1Pop && !s2Pop)
	{
		gMaxDiff = std::max(gMaxDiff, s1Min - min);
		gMaxDiff = std::max(gMaxDiff, max - s1Max);
	}
	else if (!s1Pop && !s2Pop)
	{
		gMaxDiff = std::max(gMaxDiff, max - min);
	}
	
	if (s1Pop && checkDone(s1Min, s1Max))
		return;
	if (s2Pop && checkDone(s2Min, s2Max))
		return;
	
	ll s1Diff = s1Max - s1Min;
	ll s2Diff = s2Max - s2Min;
	
	bool travS1 = s1Pop && s1Diff > gMaxDiff;
	bool travS2 = s2Pop && s2Diff > gMaxDiff;
	
	if (travS1 && travS2)
	{
		if (s1Diff > s2Diff)
		{
			maxDiff(s1Min, s1Max);
			if (s2Diff > gMaxDiff)
				maxDiff(s2Min, s2Max);
		}
		else
		{
			maxDiff(s2Min, s2Max);
			if (s1Diff > gMaxDiff)
				maxDiff(s1Min, s1Max);
		}
	}
	else
	{
		if (travS1)
			maxDiff(s1Min, s1Max);
		if (travS2)
			maxDiff(s2Min, s2Max);
	}
}

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);
		
		targetCount = N;
		
		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;
}

Compilation message (stderr)

gap.cpp: In function 'bool checkDone(ll, ll)':
gap.cpp:16:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (found.size() >= targetCount)
      ~~~~~~~~~~~~~^~~~~~~~~~~~~~

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