Submission #485161

#	Time	Username	Problem	Language	Result	Execution time	Memory
485161		MilosMilutinovic	Gap (APIO16_gap)	C++14	100 / 100	57 ms	2352 KiB

gap

#include "gap.h"
#include <bits/stdc++.h>
#define ff(i,a,b) for(int i = (a); (i) <= (b); ++(i))
#define fb(i,a,b) for(int i = (a); (i) >= (b); --(i))
#define pb push_back
#define ll long long
 
using namespace std;
 
ll findGap(int t, int n){
	if(t == 1){
		vector<ll> niz;
		ll l,r;
		MinMax(0, 1e18, &l, &r);
		niz.pb(l);
		niz.pb(r);
		ff(i,1,(n-1)/2){
			MinMax(l + 1, r - 1, &l, &r);
			if(l != -1)niz.pb(l);
			if(r != -1 && l != r)niz.pb(r);
		}
		sort(niz.begin(), niz.end());
		ll ans = 0;
		ff(i,0,n-1)ans = max(ans, niz[i + 1] - niz[i]);
		return ans;
	}
	else{
		vector<ll> niz;
		ll l,r;
		MinMax(0, 1e18, &l, &r);
		if(n == 2)return r - l;
		niz.pb(l);
		niz.pb(r);
		ll d = (r - l + n - 3) / (n - 2);
		for(ll i = l + 1; i < r; i += d){
			ll x,y;
			MinMax(i, i + d - 1, &x, &y);
			if(x != -1)niz.pb(x);
			if(y != -1 && x != y)niz.pb(y);
		}
		sort(niz.begin(), niz.end());
		niz.erase(unique(niz.begin(), niz.end()), niz.end());
		ll ans = 0;
		ff(i,0,niz.size()-1)ans = max(ans, niz[i + 1] - niz[i]);
		return ans;
	}
}

Compilation message (stderr)

gap.cpp: In function 'long long int findGap(int, int)':
gap.cpp:3:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define ff(i,a,b) for(int i = (a); (i) <= (b); ++(i))
      |                                    ~~~~^~~~~~
gap.cpp:44:3: note: in expansion of macro 'ff'
   44 |   ff(i,0,niz.size()-1)ans = max(ans, niz[i + 1] - niz[i]);
      |   ^~

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