Submission #542400

#	Time	Username	Problem	Language	Result	Execution time	Memory
542400		farhan132	Gap (APIO16_gap)	C++17	100 / 100	77 ms	5768 KiB

gap

#include "gap.h"
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef double dd;
typedef vector<ll> vll;
typedef pair<ll , ll> ii;
typedef vector< ii > vii;
typedef pair < pair < ll , ll > , pair < ll , ll > > cm; 
typedef tuple < int, ll, ll > tp;
 
#define ff first
#define ss second
#define pb push_back
#define in insert

ii get(ll x, ll y){
	ll mn , mx;
	MinMax(x, y, &mn, &mx);
	return {mn, mx};
}

long long findGap(int T, int n)
{   
	if(T == 1){
		set < ll > s;
		ll L = 0, R = 1e18;
		while(L <= R && s.size() < n){
			auto [l , r] = get(L , R);
			if(l == -1) break;
			s.in(l);
			s.in(r);
			L = l + 1;
			R = r - 1;
		}
		ll last = -1 , ans = 0;
		for(auto u : s){
			if(last != -1) ans = max(ans , u - last); last = u;
		}
		return ans;
	}
	auto [l, r] = get(0, 1e18);
	if(r - l + 1 == n) return 1;
	ll block = (((r - l + 1) - n) + n - 2) / (n - 1);
	vector < ii > v;
	ll cur = l + 1;
	ll last = l;
	ll ans = block + 1;
	while(cur <= r){
		ll L = cur , R = min(cur + block, r);
		auto [x, y] = get(L , R);
		cur = R + 1;
		if(x == -1){
			continue;
		}
		if(last != -1) ans = max(ans , x - last);
		last = y;
	}
	return ans;
}

Compilation message (stderr)

gap.cpp: In function 'long long int findGap(int, int)':
gap.cpp:31:28: warning: comparison of integer expressions of different signedness: 'std::set<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   31 |   while(L <= R && s.size() < n){
      |                   ~~~~~~~~~^~~
gap.cpp:41:4: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   41 |    if(last != -1) ans = max(ans , u - last); last = u;
      |    ^~
gap.cpp:41:46: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   41 |    if(last != -1) ans = max(ans , u - last); last = u;
      |                                              ^~~~

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