Submission #61156

#	Time	Username	Problem	Language	Result	Execution time	Memory
61156		Eae02	Gap (APIO16_gap)	C++14	19.72 / 100	86 ms	1516 KiB

gap

#include "gap.h"

#include <bits/stdc++.h>

using ll = long long;

ll gMaxDiff = 0;

void maxDiff(ll min, ll max)
{
	ll mid = min + (max - min) / 2;
	
	ll s1Min, s1Max;
	MinMax(min + 1, mid, &s1Min, &s1Max);
	bool s1Pop = s1Min != -1;
	
	ll s2Min, s2Max;
	MinMax(mid + 1, 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 && s1Max - s1Min > gMaxDiff)
		maxDiff(s1Min, s1Max);
	if (s2Pop && s2Max - s2Min > gMaxDiff)
		maxDiff(s2Min, s2Max);
}

long long findGap(int T, int N)
{
	ll min, max;
	MinMax(0, 1000000000000000000, &min, &max);
	
	maxDiff(min, max);
	
	return gMaxDiff;
}

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