Submission #238599

#	Time	Username	Problem	Language	Result	Execution time	Memory
238599		denniskim	Gap (APIO16_gap)	C++14	100 / 100	87 ms	3392 KiB

gap

#include "gap.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

long long findGap(int T, int N)
{
	vector<ll> vec;
	ll ret = 0;
	
	if(T == 1)
	{
		ll s = 0;
		ll e = 2000000000000000010;
		
		while(N >= 1)
		{
			ll minn, maxx;
			MinMax(s, e, &minn, &maxx);
			
			vec.push_back(minn);
			vec.push_back(maxx);
			
			s = minn + 1;
			e = maxx - 1;
			N -= 2;
		}
	}
	
	else
	{
		ll maxx, minn;
		MinMax(0, 2000000000000000010, &minn, &maxx);
		
		ll ho = (maxx - minn + N - 2) / (N - 1);
		ret = ho;
		
		for(ll p = minn ; p <= maxx ; p += ho + 1)
		{
			ll l, r;
			MinMax(p, p + ho, &l, &r);
			vec.push_back(l);
			vec.push_back(r);
		}
	}
	
	sort(vec.begin(), vec.end());
	
	for(int i = 1 ; i < vec.size() ; i++)
		ret = max(ret, vec[i] - vec[i - 1]);
	
	return ret;
}

Compilation message (stderr)

gap.cpp: In function 'long long int findGap(int, int)':
gap.cpp:50:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 1 ; i < vec.size() ; i++)
                  ~~^~~~~~~~~~~~

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