#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
long long findGap(int t, int n)
{
long long mx, mn;
MinMax(1, (long long)1e18, &mn, &mx);
if (t == 1){
vector <long long> a;
a.push_back(mn);
a.push_back(mx);
while ((int)a.size() < n){
MinMax(mn + 1, mx - 1, &mn, &mx);
a.push_back(mn);
if (mn != mx)
a.push_back(mx);
}
sort(a.begin(), a.end());
long long ans = 0;
for (int i = 1; i < n; i++) ans = max(ans, a[i] - a[i - 1]);
return ans;
}
long long ans = (mx - mn + n - 1) / n;
long long last = mn;
//go from s to t, but make jumps of size ans
long long curr = mn + 1;
while (curr <= mx){
//query [curr, curr + ans]
long long mi, ma;
MinMax(curr, curr + ans, &mi, &ma);
curr += ans;
if (mi == -1){
continue;
}
ans = max(mi - last, ans);
last = ma;
}
return ans;
}
| # |
결과 |
실행 시간 |
메모리 |
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 |
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 |
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 |
8 ms |
848 KB |
Output is correct |
| 17 |
Correct |
8 ms |
848 KB |
Output is correct |
| 18 |
Correct |
8 ms |
848 KB |
Output is correct |
| 19 |
Correct |
8 ms |
848 KB |
Output is correct |
| 20 |
Correct |
7 ms |
848 KB |
Output is correct |
| 21 |
Correct |
32 ms |
2252 KB |
Output is correct |
| 22 |
Correct |
31 ms |
2216 KB |
Output is correct |
| 23 |
Correct |
32 ms |
2208 KB |
Output is correct |
| 24 |
Correct |
32 ms |
2240 KB |
Output is correct |
| 25 |
Correct |
29 ms |
2208 KB |
Output is correct |
| 26 |
Correct |
32 ms |
2164 KB |
Output is correct |
| 27 |
Correct |
31 ms |
2220 KB |
Output is correct |
| 28 |
Correct |
32 ms |
2204 KB |
Output is correct |
| 29 |
Correct |
32 ms |
2200 KB |
Output is correct |
| 30 |
Correct |
26 ms |
2196 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 |
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 |
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 |
0 ms |
208 KB |
Output is correct |
| 11 |
Correct |
1 ms |
208 KB |
Output is correct |
| 12 |
Correct |
1 ms |
208 KB |
Output is correct |
| 13 |
Correct |
1 ms |
208 KB |
Output is correct |
| 14 |
Correct |
1 ms |
336 KB |
Output is correct |
| 15 |
Correct |
1 ms |
208 KB |
Output is correct |
| 16 |
Correct |
4 ms |
508 KB |
Output is correct |
| 17 |
Correct |
5 ms |
464 KB |
Output is correct |
| 18 |
Correct |
4 ms |
508 KB |
Output is correct |
| 19 |
Correct |
4 ms |
464 KB |
Output is correct |
| 20 |
Correct |
3 ms |
464 KB |
Output is correct |
| 21 |
Correct |
20 ms |
1092 KB |
Output is correct |
| 22 |
Correct |
16 ms |
1076 KB |
Output is correct |
| 23 |
Correct |
17 ms |
1020 KB |
Output is correct |
| 24 |
Correct |
17 ms |
976 KB |
Output is correct |
| 25 |
Correct |
37 ms |
1088 KB |
Output is correct |
| 26 |
Correct |
17 ms |
996 KB |
Output is correct |
| 27 |
Correct |
17 ms |
1064 KB |
Output is correct |
| 28 |
Correct |
16 ms |
1072 KB |
Output is correct |
| 29 |
Correct |
20 ms |
1020 KB |
Output is correct |
| 30 |
Correct |
14 ms |
1068 KB |
Output is correct |
| 31 |
Correct |
1 ms |
208 KB |
Output is correct |
| 32 |
Correct |
0 ms |
208 KB |
Output is correct |
