| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 529807 |
2022-02-23T17:30:37 Z |
happypotato |
Gap (APIO16_gap) |
C++17 |
|
50 ms |
1088 KB |
#include "gap.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll mn, mx;
ll st1(int n) {
ll s = 0, t = 1e18;
MinMax(s, t, &mn, &mx);
ll ans = 0;
for (ll i = 2; i <= n / 2; i++) {
ll pmn = mn, pmx = mx;
MinMax(mn + 1, mx - 1, &mn, &mx);
ans = max(ans, mn - pmn);
ans = max(ans, pmx - mx);
}
if (n % 2 == 1) {
ll fin, fin2;
MinMax(mn + 1, mx - 1, &fin, &fin2);
ans = max(ans, fin - mn);
ans = max(ans, mx - fin);
} else {
ans = max(ans, mx - mn);
}
return ans;
}
ll st2(int n) {
if (n <= 6) return st1(n);
/*
Solution outline:
Query(0, 1e18) -> n + 1 queries
n - 2 items left, given a[1] and a[n]
Idea:
spilt the range into n - 1
by pigeonhole principle, at least 1 range has no items
(and there definitely exists a range which is >= that range)
Take max(min of right range - max of left range)
*/
ll s = 0, t = 1e18;
MinMax(s, t, &mn, &mx);
s = mn + 1; t = mx - 1;
ll range = (t - s) + 1;
range /= (n - 1);
// fprintf(stderr, "Range: %lld\n", range);
ll int rs = s, rt = s + range - 1;
ll int prev = mn;
ll int ans = 0;
for (int i = 1; i <= n - 1; i++) {
MinMax(rs, rt, &mn, &mx);
// fprintf(stderr, "Query: %lld %lld, return: %lld %lld\n", rs, rt, mn, mx);
rs += range; rt += range;
if (mn == -1) continue;
ans = max(ans, mn - prev);
prev = mx;
}
if (rs <= t) {
MinMax(rs, t, &mn, &mx);
// fprintf(stderr, "[FINAL] Query: %lld %lld, return: %lld %lld\n", rs, t, mn, mx);
if (mn != -1) {
ans = max(ans, mn - prev);
ans = max(ans, (t + 1) - mx);
} else {
ans = max(ans, (t + 1) - prev);
}
}
return ans;
}
long long findGap(int T, int N) {
if (T == 1) return st1(N);
else return st2(N);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
200 KB |
Output is correct |
| 2 |
Correct |
0 ms |
200 KB |
Output is correct |
| 3 |
Correct |
0 ms |
200 KB |
Output is correct |
| 4 |
Correct |
0 ms |
200 KB |
Output is correct |
| 5 |
Correct |
0 ms |
200 KB |
Output is correct |
| 6 |
Correct |
0 ms |
200 KB |
Output is correct |
| 7 |
Correct |
0 ms |
200 KB |
Output is correct |
| 8 |
Correct |
1 ms |
200 KB |
Output is correct |
| 9 |
Correct |
0 ms |
200 KB |
Output is correct |
| 10 |
Correct |
0 ms |
200 KB |
Output is correct |
| 11 |
Correct |
1 ms |
200 KB |
Output is correct |
| 12 |
Correct |
1 ms |
200 KB |
Output is correct |
| 13 |
Correct |
1 ms |
200 KB |
Output is correct |
| 14 |
Correct |
1 ms |
200 KB |
Output is correct |
| 15 |
Correct |
1 ms |
200 KB |
Output is correct |
| 16 |
Correct |
8 ms |
456 KB |
Output is correct |
| 17 |
Correct |
9 ms |
456 KB |
Output is correct |
| 18 |
Correct |
9 ms |
456 KB |
Output is correct |
| 19 |
Correct |
9 ms |
416 KB |
Output is correct |
| 20 |
Correct |
7 ms |
456 KB |
Output is correct |
| 21 |
Correct |
33 ms |
1056 KB |
Output is correct |
| 22 |
Correct |
40 ms |
960 KB |
Output is correct |
| 23 |
Correct |
35 ms |
1044 KB |
Output is correct |
| 24 |
Correct |
34 ms |
1044 KB |
Output is correct |
| 25 |
Correct |
29 ms |
1076 KB |
Output is correct |
| 26 |
Correct |
34 ms |
1060 KB |
Output is correct |
| 27 |
Correct |
35 ms |
1044 KB |
Output is correct |
| 28 |
Correct |
33 ms |
1088 KB |
Output is correct |
| 29 |
Correct |
33 ms |
960 KB |
Output is correct |
| 30 |
Correct |
28 ms |
1008 KB |
Output is correct |
| 31 |
Correct |
0 ms |
200 KB |
Output is correct |
| 32 |
Correct |
0 ms |
200 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
200 KB |
Output is correct |
| 2 |
Correct |
0 ms |
200 KB |
Output is correct |
| 3 |
Correct |
0 ms |
200 KB |
Output is correct |
| 4 |
Correct |
0 ms |
200 KB |
Output is correct |
| 5 |
Correct |
0 ms |
200 KB |
Output is correct |
| 6 |
Correct |
0 ms |
200 KB |
Output is correct |
| 7 |
Correct |
0 ms |
200 KB |
Output is correct |
| 8 |
Correct |
0 ms |
200 KB |
Output is correct |
| 9 |
Correct |
0 ms |
200 KB |
Output is correct |
| 10 |
Correct |
0 ms |
200 KB |
Output is correct |
| 11 |
Correct |
1 ms |
200 KB |
Output is correct |
| 12 |
Correct |
1 ms |
328 KB |
Output is correct |
| 13 |
Correct |
1 ms |
200 KB |
Output is correct |
| 14 |
Correct |
1 ms |
200 KB |
Output is correct |
| 15 |
Correct |
1 ms |
200 KB |
Output is correct |
| 16 |
Correct |
11 ms |
500 KB |
Output is correct |
| 17 |
Correct |
12 ms |
500 KB |
Output is correct |
| 18 |
Correct |
12 ms |
416 KB |
Output is correct |
| 19 |
Correct |
11 ms |
380 KB |
Output is correct |
| 20 |
Correct |
6 ms |
456 KB |
Output is correct |
| 21 |
Correct |
47 ms |
960 KB |
Output is correct |
| 22 |
Correct |
48 ms |
976 KB |
Output is correct |
| 23 |
Correct |
47 ms |
988 KB |
Output is correct |
| 24 |
Correct |
48 ms |
968 KB |
Output is correct |
| 25 |
Correct |
43 ms |
1076 KB |
Output is correct |
| 26 |
Correct |
48 ms |
1072 KB |
Output is correct |
| 27 |
Correct |
50 ms |
1064 KB |
Output is correct |
| 28 |
Correct |
47 ms |
1076 KB |
Output is correct |
| 29 |
Correct |
47 ms |
1040 KB |
Output is correct |
| 30 |
Correct |
24 ms |
968 KB |
Output is correct |
| 31 |
Correct |
0 ms |
200 KB |
Output is correct |
| 32 |
Correct |
0 ms |
200 KB |
Output is correct |
