oj.uz

Submission #739362

# Submission time Handle Problem Language Result Execution time Memory
739362 2023-05-10T11:07:26 Z Nahian9696 Gap (APIO16_gap) C++17
100 / 100
 86 ms 5928 KB 
#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

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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 1 ms 208 KB Output is correct
6 Correct 0 ms 208 KB Output is correct
7 Correct 1 ms 208 KB Output is correct
8 Correct 1 ms 208 KB Output is correct
9 Correct 0 ms 208 KB Output is correct
10 Correct 0 ms 208 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 336 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 13 ms 1576 KB Output is correct
17 Correct 13 ms 1652 KB Output is correct
18 Correct 14 ms 1568 KB Output is correct
19 Correct 14 ms 1568 KB Output is correct
20 Correct 11 ms 1616 KB Output is correct
21 Correct 54 ms 5664 KB Output is correct
22 Correct 56 ms 5740 KB Output is correct
23 Correct 54 ms 5652 KB Output is correct
24 Correct 54 ms 5676 KB Output is correct
25 Correct 64 ms 5712 KB Output is correct
26 Correct 60 ms 5664 KB Output is correct
27 Correct 56 ms 5684 KB Output is correct
28 Correct 58 ms 5756 KB Output is correct
29 Correct 65 ms 5704 KB Output is correct
30 Correct 47 ms 5696 KB Output is correct
31 Correct 0 ms 208 KB Output is correct
32 Correct 0 ms 208 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 0 ms 208 KB Output is correct
6 Correct 1 ms 208 KB Output is correct
7 Correct 1 ms 208 KB Output is correct
8 Correct 0 ms 208 KB Output is correct
9 Correct 0 ms 208 KB Output is correct
10 Correct 0 ms 208 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 396 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 336 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 16 ms 1488 KB Output is correct
17 Correct 19 ms 1532 KB Output is correct
18 Correct 19 ms 1456 KB Output is correct
19 Correct 17 ms 1448 KB Output is correct
20 Correct 6 ms 564 KB Output is correct
21 Correct 72 ms 5284 KB Output is correct
22 Correct 72 ms 5264 KB Output is correct
23 Correct 74 ms 5260 KB Output is correct
24 Correct 73 ms 5200 KB Output is correct
25 Correct 86 ms 5928 KB Output is correct
26 Correct 74 ms 5200 KB Output is correct
27 Correct 85 ms 5272 KB Output is correct
28 Correct 74 ms 5204 KB Output is correct
29 Correct 71 ms 5248 KB Output is correct
30 Correct 28 ms 1824 KB Output is correct
31 Correct 0 ms 208 KB Output is correct
32 Correct 1 ms 208 KB Output is correct