Submission #68126

#	Time	Username	Problem	Language	Result	Execution time	Memory
68126		shoemakerjo	Gap (APIO16_gap)	C++14	100 / 100	91 ms	3568 KiB

gap

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

using namespace std;
#define ll long long

ll findGap(int T, int N)
{
	if (T == 1) {
		vector<ll> nums;
		ll lo = 1;
		ll hi = 1000000000000000000LL;
		int tseen = 0;
		while (lo < hi) {
			ll c1, c2;
			MinMax(lo, hi, &c1, &c2);
			nums.push_back(c1);
			nums.push_back(c2);
			tseen += 2;
			if (tseen >= N) break;
			lo = c1+1;
			hi = c2-1;
		}
		ll ans = 0LL;
		sort(nums.begin(), nums.end());
		for (int i = 1; i < nums.size(); i++) {
			ans = max(ans, nums[i]-nums[i-1]);
		}
		return ans;
	}

	//this is for T = 2

	ll lo, hi;
	MinMax(1, 1000000000000000000LL, &lo, &hi);
	ll alph = (hi-lo)/N;
	if ((hi-lo)%N != 0) alph+=1LL;
	vector<ll> nums; //all the ones we care about
	ll st = lo+1LL;
	nums.push_back(lo);
	while (st <= hi) {
		ll c1, c2;
		MinMax(st, st+alph, &c1, &c2);
		if (c1 != -1) {
			nums.push_back(c1);
			nums.push_back(c2);
		}
		st += alph+1LL;
	}
	ll ans = alph;
	for (int i = 1; i < nums.size(); i++) {
		ans = max(ans, nums[i]-nums[i-1]);
	}

	return ans;
}

Compilation message (stderr)

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

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