Submission #598340

#	Time	Username	Problem	Language	Result	Execution time	Memory
598340		8e7	Gap (APIO16_gap)	C++17	100 / 100	61 ms	3260 KiB

gap

//Challenge: Accepted
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include "gap.h"
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 50005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
const ll inf = 1e18;
ll findGap(int T, int N) {
	ll ret = 0;
	vector<ll> a;
	if (T == 1) {
		ll low = 0, up = inf, vl, vr;
		while (low < up && a.size() < N) {
			MinMax(low, up, &vl, &vr);
			if (vl == -1) break;
			a.push_back(vl);
			a.push_back(vr);
			low = vl+1, up = vr-1;
		}
	} else {
		ll mi, ma;	
		MinMax(0, inf, &mi, &ma);
		a.push_back(mi);
		ll lef = mi+1;
		for (int i = 0;i < N-1;i++) {
			ll d = (ma - lef) / (N - 1 - i);
			ll rig = lef + d - 1, vl, vr;
			MinMax(lef, rig, &vl, &vr);
			lef += d;
			if (vl != -1) {
				a.push_back(vl);
				a.push_back(vr);
			}
		}
		a.push_back(ma);
	}
	sort(a.begin(), a.end());
	a.resize(int(unique(a.begin(), a.end()) - a.begin()));
	for (int i = 1;i < a.size();i++) ret = max(ret, a[i] - a[i-1]);
	return ret;
}

Compilation message (stderr)

gap.cpp: In function 'long long int findGap(int, int)':
gap.cpp:29:31: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   29 |   while (low < up && a.size() < N) {
      |                      ~~~~~~~~~^~~
gap.cpp:55:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |  for (int i = 1;i < a.size();i++) ret = max(ret, a[i] - a[i-1]);
      |                 ~~^~~~~~~~~~

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