Submission #197003

#	Time	Username	Problem	Language	Result	Execution time	Memory
197003		Juney	Gap (APIO16_gap)	C++14	100 / 100	82 ms	2292 KiB

gap

#include "gap.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

void f(ll s, ll t, ll &a, ll &b) { MinMax(s, t, &a, &b); }

ll findGap(int T, int N) {
	if(T == 1) {
		ll l = 0, r = 1e18;
		vector<ll> v;
		for(int i=1; i<=(N+1)/2; i++) {
			if(l > r) break;
			ll a, b; f(l, r, a, b);
			if(a != -1) v.push_back(a);
			if(b != -1 && a != b) v.push_back(b);
			l = a + 1; r = b - 1;
		}
		sort(v.begin(), v.end());
		ll ans = 0;
		for(int i=1; i<v.size(); i++) ans = max(ans, v[i] - v[i-1]);
		return ans;
	}
	else {
		ll l, r;
		f(0, (ll)1e18, l, r);
		ll sz = (r - l) / (N-1);
		ll s = l, e = l + sz;
		vector<ll> v;
		for(int i=1; i<=N-1; i++) {
			if(s > e) break;
			ll a, b; f(s, e, a, b);
			if(a != -1) v.push_back(a);
			if(b != -1 && a != b) v.push_back(b);
			s = e + 1; e = min(r, s + sz);
		}
		ll ans = 0;
		for(int i=1; i<v.size(); i++) ans = max(ans, v[i] - v[i-1]);
		return ans;
	}
}

Compilation message (stderr)

gap.cpp: In function 'll findGap(int, int)':
gap.cpp:22:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=1; i<v.size(); i++) ans = max(ans, v[i] - v[i-1]);
                ~^~~~~~~~~
gap.cpp:39:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=1; i<v.size(); i++) ans = max(ans, v[i] - v[i-1]);
                ~^~~~~~~~~

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