| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 529801 |
2022-02-23T17:24:04 Z |
happypotato |
Gap (APIO16_gap) |
C++17 |
|
54 ms |
1176 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) {
/*
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 = 0; i < n - 2; 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;
}
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 |
1 ms |
200 KB |
Output is correct |
| 3 |
Correct |
0 ms |
264 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 |
1 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 |
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 |
9 ms |
492 KB |
Output is correct |
| 17 |
Correct |
9 ms |
504 KB |
Output is correct |
| 18 |
Correct |
11 ms |
492 KB |
Output is correct |
| 19 |
Correct |
11 ms |
620 KB |
Output is correct |
| 20 |
Correct |
6 ms |
504 KB |
Output is correct |
| 21 |
Correct |
34 ms |
1048 KB |
Output is correct |
| 22 |
Correct |
36 ms |
988 KB |
Output is correct |
| 23 |
Correct |
35 ms |
1072 KB |
Output is correct |
| 24 |
Correct |
44 ms |
1072 KB |
Output is correct |
| 25 |
Correct |
32 ms |
1176 KB |
Output is correct |
| 26 |
Correct |
34 ms |
1052 KB |
Output is correct |
| 27 |
Correct |
35 ms |
964 KB |
Output is correct |
| 28 |
Correct |
42 ms |
1056 KB |
Output is correct |
| 29 |
Correct |
45 ms |
1052 KB |
Output is correct |
| 30 |
Correct |
27 ms |
1088 KB |
Output is correct |
| 31 |
Correct |
0 ms |
212 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 |
1 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 |
1 ms |
200 KB |
Output is correct |
| 7 |
Correct |
1 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 |
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 |
15 ms |
448 KB |
Output is correct |
| 17 |
Correct |
13 ms |
456 KB |
Output is correct |
| 18 |
Correct |
15 ms |
456 KB |
Output is correct |
| 19 |
Correct |
12 ms |
504 KB |
Output is correct |
| 20 |
Correct |
6 ms |
456 KB |
Output is correct |
| 21 |
Correct |
48 ms |
1076 KB |
Output is correct |
| 22 |
Correct |
47 ms |
1028 KB |
Output is correct |
| 23 |
Correct |
50 ms |
1076 KB |
Output is correct |
| 24 |
Correct |
49 ms |
1048 KB |
Output is correct |
| 25 |
Correct |
45 ms |
1052 KB |
Output is correct |
| 26 |
Correct |
49 ms |
1052 KB |
Output is correct |
| 27 |
Correct |
54 ms |
1064 KB |
Output is correct |
| 28 |
Correct |
49 ms |
1068 KB |
Output is correct |
| 29 |
Correct |
48 ms |
1096 KB |
Output is correct |
| 30 |
Correct |
28 ms |
1084 KB |
Output is correct |
| 31 |
Correct |
1 ms |
200 KB |
Output is correct |
| 32 |
Correct |
0 ms |
200 KB |
Output is correct |
