Submission #546087

#	Time	Username	Problem	Language	Result	Execution time	Memory
546087		Hanksburger	Gap (APIO16_gap)	C++17	100 / 100	70 ms	2328 KiB

gap

#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
vector<long long> vec;
long long a[100005];
long long findGap(int t, int n)
{
	if (t==1)
	{
		long long l=1, r=1e18, ans=0;
		for (int i=1; i<=n/2; i++)
		{
			MinMax(l, r, &a[i], &a[n-i+1]);
			l=a[i]+1;
			r=a[n-i+1]-1;
		}
		if (n&1)
			MinMax(l, r, &a[n/2+1], &a[n/2+1]);
		for (int i=2; i<=n; i++)
			ans=max(ans, a[i]-a[i-1]);
		return ans;
	}
	else
	{
		long long l, r, num, ans=0;
		MinMax(1, 1e18, &l, &r);
		vec.push_back(l);
		vec.push_back(r);
		num=(r-l-1)/(n-1)+1;
		for (long long i=l+1; i<r; i+=num+1)
		{
			long long j=min(r-1, i+num), resL, resR;
			MinMax(i, j, &resL, &resR);
			if (resL!=-1)
				vec.push_back(resL);
			if (resR!=resL)
				vec.push_back(resR);
		}
		sort(vec.begin(), vec.end());
		for (int i=1; i<vec.size(); i++)
			ans=max(ans, vec[i]-vec[i-1]);
		return ans;
	}
}

Compilation message (stderr)

gap.cpp: In function 'long long int findGap(int, int)':
gap.cpp:40:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |   for (int i=1; i<vec.size(); i++)
      |                 ~^~~~~~~~~~~

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