| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 792593 |
2023-07-25T07:15:11 Z |
IvanJ |
Gap (APIO16_gap) |
C++17 |
|
46 ms |
2332 KB |
#include "gap.h"
#include<bits/stdc++.h>
#define pb push_back
#define x first
#define y second
#define all(a) (a).begin(), (a).end()
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
ll findGap(int T, int N) {
if(T == 1) {
ll lo = 0, hi = 1e18, mini = 0;
vector<ll> a;
int sz = N;
while(hi - lo >= mini) {
MinMax(lo, hi, &lo, &hi);
if(sz == 1) {
a.pb(lo);
break;
}
mini = max(mini, (hi - lo) / ((ll)sz - 1));
a.pb(lo), a.pb(hi);
sz -= 2;
if(lo == hi) sz++;
lo++, hi--;
}
sort(all(a));
ll ans = 0;
for(int i = 1;i < (int)a.size();i++)
ans = max(ans, a[i] - a[i - 1]);
return ans;
}
if(T == 2) {
ll lo = 0, hi = 1e18;
MinMax(lo, hi, &lo, &hi);
ll min_gap = (hi - lo) / ((ll)N - 1);
ll ans = 0;
ll x = lo + 1, lst = lo, l, r;
while(x < hi) {
MinMax(x, x + min_gap, &l, &r);
if(l != -1)
ans = max(ans, l - lst);
x += min_gap + 1;
if(r != -1) lst = r;
}
if(x == hi) ans = max(ans, hi - lst);
return ans;
}
}
Compilation message
gap.cpp: In function 'll findGap(int, int)':
gap.cpp:54:1: warning: control reaches end of non-void function [-Wreturn-type]
54 | }
| ^
| # |
Verdict |
Execution time |
Memory |
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 |
288 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 |
920 KB |
Output is correct |
| 17 |
Correct |
8 ms |
848 KB |
Output is correct |
| 18 |
Correct |
10 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 |
38 ms |
2152 KB |
Output is correct |
| 22 |
Correct |
31 ms |
2220 KB |
Output is correct |
| 23 |
Correct |
32 ms |
2240 KB |
Output is correct |
| 24 |
Correct |
32 ms |
2248 KB |
Output is correct |
| 25 |
Correct |
33 ms |
2332 KB |
Output is correct |
| 26 |
Correct |
33 ms |
2176 KB |
Output is correct |
| 27 |
Correct |
31 ms |
2196 KB |
Output is correct |
| 28 |
Correct |
33 ms |
2248 KB |
Output is correct |
| 29 |
Correct |
31 ms |
2204 KB |
Output is correct |
| 30 |
Correct |
30 ms |
2220 KB |
Output is correct |
| 31 |
Correct |
1 ms |
208 KB |
Output is correct |
| 32 |
Correct |
0 ms |
208 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
208 KB |
Output is correct |
| 2 |
Correct |
0 ms |
216 KB |
Output is correct |
| 3 |
Correct |
0 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 |
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 |
336 KB |
Output is correct |
| 16 |
Correct |
10 ms |
512 KB |
Output is correct |
| 17 |
Correct |
11 ms |
720 KB |
Output is correct |
| 18 |
Correct |
10 ms |
540 KB |
Output is correct |
| 19 |
Correct |
11 ms |
516 KB |
Output is correct |
| 20 |
Correct |
5 ms |
464 KB |
Output is correct |
| 21 |
Correct |
40 ms |
1084 KB |
Output is correct |
| 22 |
Correct |
41 ms |
1084 KB |
Output is correct |
| 23 |
Correct |
46 ms |
1080 KB |
Output is correct |
| 24 |
Correct |
46 ms |
1080 KB |
Output is correct |
| 25 |
Correct |
37 ms |
976 KB |
Output is correct |
| 26 |
Correct |
43 ms |
1040 KB |
Output is correct |
| 27 |
Correct |
40 ms |
1096 KB |
Output is correct |
| 28 |
Correct |
45 ms |
1084 KB |
Output is correct |
| 29 |
Correct |
40 ms |
1060 KB |
Output is correct |
| 30 |
Correct |
21 ms |
1060 KB |
Output is correct |
| 31 |
Correct |
0 ms |
208 KB |
Output is correct |
| 32 |
Correct |
0 ms |
208 KB |
Output is correct |
