#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
using ll = long long;
ll findGap(int T, int N) {
if (T == 1) {
ll x, y, l = 0, r = (ll)1e18, ans = 0;
vector<ll> lh, rh, all;
while (l <= r && lh.size() + rh.size() < N) {
MinMax(l, r, &x, &y);
if (x == -1) break;
lh.pb(x);
if (x != y) rh.pb(y);
l = x + 1;
r = y - 1;
}
reverse(rh.begin(), rh.end());
for (auto i : lh) all.pb(i);
for (auto i : rh) all.pb(i);
for (int i = 1; i < (int)all.size(); i++) {
ans = max(ans, all[i] - all[i - 1]);
}
return ans;
} else {
ll x, y;
MinMax(0, (ll)1e18, &x, &y);
ll k = (y - x + N - 2) / (N - 1), ans = 0;
vector<ll> seq;
seq.pb(x);
for (ll p = x; p < y; p += k) {
ll x2, y2;
MinMax(p + 1, p + k, &x2, &y2);
if (x2 != -1) {
seq.pb(x2);
seq.pb(y2);
}
}
seq.pb(y);
for (int i = 1; i < (int)seq.size(); i++) {
ans = max(ans, seq[i] - seq[i - 1]);
}
return ans;
}
}
Compilation message
gap.cpp: In function 'll findGap(int, int)':
gap.cpp:13:42: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
13 | while (l <= r && lh.size() + rh.size() < N) {
| ~~~~~~~~~~~~~~~~~~~~~~^~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
208 KB |
Output is correct |
| 2 |
Correct |
0 ms |
208 KB |
Output is correct |
| 3 |
Correct |
1 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 |
0 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 |
1 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 |
332 KB |
Output is correct |
| 14 |
Correct |
1 ms |
336 KB |
Output is correct |
| 15 |
Correct |
1 ms |
336 KB |
Output is correct |
| 16 |
Correct |
9 ms |
1168 KB |
Output is correct |
| 17 |
Correct |
7 ms |
1128 KB |
Output is correct |
| 18 |
Correct |
8 ms |
1128 KB |
Output is correct |
| 19 |
Correct |
9 ms |
1112 KB |
Output is correct |
| 20 |
Correct |
6 ms |
1140 KB |
Output is correct |
| 21 |
Correct |
35 ms |
2984 KB |
Output is correct |
| 22 |
Correct |
28 ms |
3028 KB |
Output is correct |
| 23 |
Correct |
36 ms |
3004 KB |
Output is correct |
| 24 |
Correct |
31 ms |
3004 KB |
Output is correct |
| 25 |
Correct |
27 ms |
2936 KB |
Output is correct |
| 26 |
Correct |
30 ms |
3004 KB |
Output is correct |
| 27 |
Correct |
31 ms |
2952 KB |
Output is correct |
| 28 |
Correct |
35 ms |
2968 KB |
Output is correct |
| 29 |
Correct |
29 ms |
3012 KB |
Output is correct |
| 30 |
Correct |
24 ms |
3048 KB |
Output is correct |
| 31 |
Correct |
0 ms |
208 KB |
Output is correct |
| 32 |
Correct |
0 ms |
208 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
208 KB |
Output is correct |
| 2 |
Correct |
0 ms |
208 KB |
Output is correct |
| 3 |
Correct |
1 ms |
208 KB |
Output is correct |
| 4 |
Correct |
1 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 |
0 ms |
336 KB |
Output is correct |
| 8 |
Correct |
0 ms |
208 KB |
Output is correct |
| 9 |
Correct |
0 ms |
208 KB |
Output is correct |
| 10 |
Correct |
1 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 |
10 ms |
848 KB |
Output is correct |
| 17 |
Correct |
10 ms |
808 KB |
Output is correct |
| 18 |
Correct |
11 ms |
848 KB |
Output is correct |
| 19 |
Correct |
10 ms |
848 KB |
Output is correct |
| 20 |
Correct |
5 ms |
448 KB |
Output is correct |
| 21 |
Correct |
47 ms |
2160 KB |
Output is correct |
| 22 |
Correct |
48 ms |
2164 KB |
Output is correct |
| 23 |
Correct |
41 ms |
2172 KB |
Output is correct |
| 24 |
Correct |
41 ms |
2224 KB |
Output is correct |
| 25 |
Correct |
51 ms |
3268 KB |
Output is correct |
| 26 |
Correct |
41 ms |
2200 KB |
Output is correct |
| 27 |
Correct |
41 ms |
2244 KB |
Output is correct |
| 28 |
Correct |
41 ms |
2260 KB |
Output is correct |
| 29 |
Correct |
41 ms |
2240 KB |
Output is correct |
| 30 |
Correct |
22 ms |
1452 KB |
Output is correct |
| 31 |
Correct |
0 ms |
208 KB |
Output is correct |
| 32 |
Correct |
0 ms |
208 KB |
Output is correct |
