Submission #739362

#	Time	Username	Problem	Language	Result	Execution time	Memory
739362		Nahian9696	Gap (APIO16_gap)	C++17	100 / 100	86 ms	5928 KiB

gap

#include "gap.h"

#include <bits/stdc++.h>

using namespace std;

typedef long double                         ld;
typedef long long                           lli;
typedef long long                           ll;
typedef vector<int32_t>                     vi;
typedef vector<ld>                          vld;
typedef vector<lli>                         vlli;
typedef pair<lli, lli>                      pii;


// #define int                                 int64_t
#define endl                                "\n"
#define inp(n)                              lli n; cin >> n
#define inpstr(s)                           string s; cin >> s
#define inp2(a,b)                           lli a,b; cin >> a >> b
#define inparr(arr,n)                       lli arr[n]; f0(t_ind, n) cin >> arr[t_ind]
#define f0(i,n)                             for(int32_t i = 0; i <  (n); i++)
#define f1(i,n)                             for(int32_t i = 1; i <= (n); i++)

#define testIn                              cin >> test
#define tests                               for(int32_t testNo=1; testNo <= (test); testNo++)

#define all(x)                              (x).begin(), (x).end()
#define rall(x)                             (x).rbegin(), (x).rend()
#define len(a)                              ((int64_t)(a).size())
#define lcm(a, b)                           (((a)*(b))/gcd(a,b))
#define ff                                  first
#define ss                                  second

#define Yes                                 cout << "Yes" << endl
#define No                                  cout << "No" << endl
#define YES                                 cout << "YES" << endl
#define NO                                  cout << "NO" << endl
#define finish                              return 0
#define clean                               fflush(stdout)

#define Inf                                 (lli)(1e9)
#define Eps                                 (ld)(1e-9)
#define PI                                  (ld)(3.141592653589793238462643383279502884197169L)
#define MOD                                 (int32_t)(1e9+7)


template<typename dataType1>
inline void print(dataType1 a) {cout << a << endl;}
template<typename dataType1, typename dataType2>
inline void print(dataType1 a, dataType2 b) {cout << a << " " << b << endl;}
template<typename dataType1, typename dataType2, typename dataType3>
inline void print(dataType1 a, dataType2 b, dataType3 c) {cout << a << " " << b << " " << c << endl;}
template<typename dataType1, typename dataType2, typename dataType3, typename dataType4>
inline void print(dataType1 a, dataType2 b, dataType3 c, dataType4 d) {cout << a << " " << b << " " << c << " " << d << endl;}
template<typename dataType>
inline dataType abs(dataType k) {if (k >= 0) return k; else return (-k);}
template<typename dataType>
inline bool isEqual(dataType a, dataType b) {return (abs((dataType)(a-b)) < 1e-9);}




set<ll> nums;


long long findGap(int T, int N) {

	ll mn, mx;

	if(N == 2) {
		MinMax(0, 1e18, &mn, &mx);
		return mx - mn;
	}
	
	if(T == 1) {
		MinMax(0, 1e18, &mn, &mx);
		nums.insert(mn), nums.insert(mx);
		while(true) {
			MinMax(mn+1, mx-1, &mn, &mx);
			if(mn == -1) break;
			nums.insert(mn), nums.insert(mx);
			if(mn + 1 >= mx) break;
			if(nums.size() == N) break;
		}
	}

	if(T == 2) {
		MinMax(0, 1e18, &mn, &mx);
		nums.insert(mn);
		nums.insert(mx);
		ll l = mn + 1, r = mx - 1;
		N -= 2;


		ll B = r - l + N;
		B /= N;
		if(B == 1) B++;

		while(l <= r) {
			MinMax(l, min(l+B-1, r), &mn, &mx);
			if(mn != -1) {
				nums.insert(mn);
				nums.insert(mx);
			}

			l += B;
			if(nums.size() == N+2) break;
		}
	}

	ll ans = 0;
	N = nums.size() - 1;
	auto it = nums.begin();

	f0(i, N) {
		ans = max(ans, *next(it) - *it);
		it = next(it);
	}

	return ans;

	return 0;
}

Compilation message (stderr)

gap.cpp: In function 'long long int findGap(int, int)':
gap.cpp:84:19: warning: comparison of integer expressions of different signedness: 'std::set<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   84 |    if(nums.size() == N) break;
      |       ~~~~~~~~~~~~^~~~
gap.cpp:108:19: warning: comparison of integer expressions of different signedness: 'std::set<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  108 |    if(nums.size() == N+2) break;
      |       ~~~~~~~~~~~~^~~~~~

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