| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 409236 |
2021-05-20T11:48:07 Z |
tranxuanbach |
Gap (APIO16_gap) |
C++17 |
|
67 ms |
1184 KB |
#include "gap.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define endl '\n'
#define fi first
#define se second
#define For(i, l, r) for (int i = l; i < r; i++)
#define ForE(i, l, r) for (int i = l; i <= r; i++)
#define FordE(i, l, r) for (int i = l; i >= r; i--)
#define Fora(v, a) for (auto v: a)
#define bend(a) a.begin(), a.end()
#define isz(a) ((signed)a.size())
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
typedef vector <int> vi;
typedef vector <pii> vpii;
typedef vector <vi> vvi;
ll findGap(int t, int n){
if (t == 1){
ll prevmn = -1, prevmx = 1000000000000000001ll, ans = 0;
ForE(i, 1, (n + 1) / 2){
ll mn, mx;
MinMax(prevmn + 1, prevmx - 1, &mn, &mx);
if (prevmn != -1){
ans = max(ans, mn - prevmn);
ans = max(ans, prevmx - mx);
}
prevmn = mn; prevmx = mx;
}
if (n % 2 == 0){
ans = max(ans, prevmx - prevmn);
}
return ans;
}
ll mn, mx, chadmn, chadmx, ans = 0;
MinMax(0, 1000000000000000000ll, &mn, &mx);
if (n == 2){
return mx - mn;
}
if (mx - mn == n - 1){
return 1;
}
ll range = (mx - mn + n - 2) / (n - 1) - 1;
ll idx = mn + 1;
chadmn = mn; chadmx = mx;
ll l = chadmn;
while (idx < chadmx){
MinMax(idx, min(idx + range, chadmx - 1), &mn, &mx);
if (mn != -1){
ans = max(ans, mn - l);
l = mx;
}
idx += range + 1;
}
ans = max(ans, chadmx - l);
return ans;
}
/* g++ gap.cpp grader.cpp -o gap -O2 -static -std=c++11
==================================================+
INPUT: |
--------------------------------------------------|
1 4
2 3 6 8
--------------------------------------------------|
==================================================+
OUTPUT: |
--------------------------------------------------|
--------------------------------------------------|
==================================================+
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
200 KB |
Output is correct |
| 2 |
Correct |
1 ms |
200 KB |
Output is correct |
| 3 |
Correct |
1 ms |
200 KB |
Output is correct |
| 4 |
Correct |
1 ms |
200 KB |
Output is correct |
| 5 |
Correct |
1 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 |
1 ms |
200 KB |
Output is correct |
| 9 |
Correct |
1 ms |
200 KB |
Output is correct |
| 10 |
Correct |
1 ms |
200 KB |
Output is correct |
| 11 |
Correct |
1 ms |
328 KB |
Output is correct |
| 12 |
Correct |
1 ms |
328 KB |
Output is correct |
| 13 |
Correct |
1 ms |
328 KB |
Output is correct |
| 14 |
Correct |
1 ms |
200 KB |
Output is correct |
| 15 |
Correct |
2 ms |
328 KB |
Output is correct |
| 16 |
Correct |
12 ms |
456 KB |
Output is correct |
| 17 |
Correct |
11 ms |
504 KB |
Output is correct |
| 18 |
Correct |
12 ms |
512 KB |
Output is correct |
| 19 |
Correct |
11 ms |
456 KB |
Output is correct |
| 20 |
Correct |
9 ms |
456 KB |
Output is correct |
| 21 |
Correct |
50 ms |
1008 KB |
Output is correct |
| 22 |
Correct |
44 ms |
948 KB |
Output is correct |
| 23 |
Correct |
47 ms |
1096 KB |
Output is correct |
| 24 |
Correct |
44 ms |
1048 KB |
Output is correct |
| 25 |
Correct |
41 ms |
1000 KB |
Output is correct |
| 26 |
Correct |
43 ms |
1048 KB |
Output is correct |
| 27 |
Correct |
44 ms |
1072 KB |
Output is correct |
| 28 |
Correct |
49 ms |
1056 KB |
Output is correct |
| 29 |
Correct |
45 ms |
976 KB |
Output is correct |
| 30 |
Correct |
35 ms |
996 KB |
Output is correct |
| 31 |
Correct |
1 ms |
200 KB |
Output is correct |
| 32 |
Correct |
1 ms |
200 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
200 KB |
Output is correct |
| 2 |
Correct |
1 ms |
200 KB |
Output is correct |
| 3 |
Correct |
1 ms |
200 KB |
Output is correct |
| 4 |
Correct |
1 ms |
200 KB |
Output is correct |
| 5 |
Correct |
1 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 |
1 ms |
200 KB |
Output is correct |
| 9 |
Correct |
1 ms |
200 KB |
Output is correct |
| 10 |
Correct |
1 ms |
200 KB |
Output is correct |
| 11 |
Correct |
2 ms |
200 KB |
Output is correct |
| 12 |
Correct |
2 ms |
200 KB |
Output is correct |
| 13 |
Correct |
1 ms |
328 KB |
Output is correct |
| 14 |
Correct |
2 ms |
200 KB |
Output is correct |
| 15 |
Correct |
1 ms |
328 KB |
Output is correct |
| 16 |
Correct |
15 ms |
544 KB |
Output is correct |
| 17 |
Correct |
19 ms |
544 KB |
Output is correct |
| 18 |
Correct |
15 ms |
504 KB |
Output is correct |
| 19 |
Correct |
16 ms |
428 KB |
Output is correct |
| 20 |
Correct |
8 ms |
456 KB |
Output is correct |
| 21 |
Correct |
60 ms |
1060 KB |
Output is correct |
| 22 |
Correct |
59 ms |
988 KB |
Output is correct |
| 23 |
Correct |
65 ms |
960 KB |
Output is correct |
| 24 |
Correct |
67 ms |
1184 KB |
Output is correct |
| 25 |
Correct |
54 ms |
1056 KB |
Output is correct |
| 26 |
Correct |
61 ms |
1056 KB |
Output is correct |
| 27 |
Correct |
59 ms |
1056 KB |
Output is correct |
| 28 |
Correct |
59 ms |
960 KB |
Output is correct |
| 29 |
Correct |
62 ms |
1092 KB |
Output is correct |
| 30 |
Correct |
33 ms |
1072 KB |
Output is correct |
| 31 |
Correct |
1 ms |
200 KB |
Output is correct |
| 32 |
Correct |
1 ms |
200 KB |
Output is correct |
