| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 371488 |
2021-02-26T18:48:29 Z |
BartolM |
Gap (APIO16_gap) |
C++17 |
|
68 ms |
1388 KB |
#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;
pll query(ll a, ll b) {
if (a>b) return mp(-1, -1);
ll x, y;
// printf("[%lld, %lld]\n", a, b);
MinMax(a, b, &x, &y);
return mp(x, y);
}
long long findGap(int T, int N) {
ll sol=0;
pll pp=query(0, 1e18);
ll MIN=pp.X, MAX=pp.Y;
if (T==1) {
N-=2;
while (N>=1) {
pll curr=query(pp.X+1, pp.Y-1);
if (curr.X==-1) break;
sol=max(sol, curr.X-pp.X);
sol=max(sol, pp.Y-curr.Y);
pp=curr;
N-=2;
}
sol=max(sol, pp.Y-pp.X);
}
else {
ll d=(MAX-MIN)/(N-1);
ll pr=MIN;
ll l=MIN, r=MIN;
while (r!=MAX) {
l=r+1; r=min(l+d, MAX);
pll ans=query(l, r);
if (ans.X!=-1) {
sol=max(sol, ans.X-pr);
pr=ans.Y;
}
if (r==MAX && ans.X!=-1) sol=max(sol, MAX-ans.Y);
}
}
return sol;
}
/*
1 8
1 5 9 18 32 46 55 63
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
364 KB |
Output is correct |
| 4 |
Correct |
1 ms |
364 KB |
Output is correct |
| 5 |
Correct |
1 ms |
364 KB |
Output is correct |
| 6 |
Correct |
0 ms |
364 KB |
Output is correct |
| 7 |
Correct |
1 ms |
384 KB |
Output is correct |
| 8 |
Correct |
0 ms |
364 KB |
Output is correct |
| 9 |
Correct |
1 ms |
364 KB |
Output is correct |
| 10 |
Correct |
1 ms |
364 KB |
Output is correct |
| 11 |
Correct |
2 ms |
364 KB |
Output is correct |
| 12 |
Correct |
2 ms |
364 KB |
Output is correct |
| 13 |
Correct |
1 ms |
364 KB |
Output is correct |
| 14 |
Correct |
1 ms |
364 KB |
Output is correct |
| 15 |
Correct |
1 ms |
364 KB |
Output is correct |
| 16 |
Correct |
13 ms |
492 KB |
Output is correct |
| 17 |
Correct |
11 ms |
492 KB |
Output is correct |
| 18 |
Correct |
12 ms |
640 KB |
Output is correct |
| 19 |
Correct |
13 ms |
492 KB |
Output is correct |
| 20 |
Correct |
9 ms |
620 KB |
Output is correct |
| 21 |
Correct |
50 ms |
1132 KB |
Output is correct |
| 22 |
Correct |
52 ms |
1132 KB |
Output is correct |
| 23 |
Correct |
45 ms |
1132 KB |
Output is correct |
| 24 |
Correct |
51 ms |
1076 KB |
Output is correct |
| 25 |
Correct |
39 ms |
1132 KB |
Output is correct |
| 26 |
Correct |
45 ms |
1168 KB |
Output is correct |
| 27 |
Correct |
48 ms |
1132 KB |
Output is correct |
| 28 |
Correct |
45 ms |
1132 KB |
Output is correct |
| 29 |
Correct |
44 ms |
1176 KB |
Output is correct |
| 30 |
Correct |
36 ms |
1260 KB |
Output is correct |
| 31 |
Correct |
1 ms |
364 KB |
Output is correct |
| 32 |
Correct |
1 ms |
364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
364 KB |
Output is correct |
| 4 |
Correct |
1 ms |
364 KB |
Output is correct |
| 5 |
Correct |
0 ms |
364 KB |
Output is correct |
| 6 |
Correct |
1 ms |
364 KB |
Output is correct |
| 7 |
Correct |
1 ms |
364 KB |
Output is correct |
| 8 |
Correct |
1 ms |
364 KB |
Output is correct |
| 9 |
Correct |
1 ms |
364 KB |
Output is correct |
| 10 |
Correct |
1 ms |
364 KB |
Output is correct |
| 11 |
Correct |
1 ms |
364 KB |
Output is correct |
| 12 |
Correct |
1 ms |
492 KB |
Output is correct |
| 13 |
Correct |
1 ms |
364 KB |
Output is correct |
| 14 |
Correct |
1 ms |
364 KB |
Output is correct |
| 15 |
Correct |
1 ms |
364 KB |
Output is correct |
| 16 |
Correct |
15 ms |
736 KB |
Output is correct |
| 17 |
Correct |
15 ms |
492 KB |
Output is correct |
| 18 |
Correct |
15 ms |
492 KB |
Output is correct |
| 19 |
Correct |
15 ms |
492 KB |
Output is correct |
| 20 |
Correct |
7 ms |
492 KB |
Output is correct |
| 21 |
Correct |
63 ms |
1260 KB |
Output is correct |
| 22 |
Correct |
67 ms |
1260 KB |
Output is correct |
| 23 |
Correct |
63 ms |
1156 KB |
Output is correct |
| 24 |
Correct |
63 ms |
1132 KB |
Output is correct |
| 25 |
Correct |
58 ms |
1132 KB |
Output is correct |
| 26 |
Correct |
63 ms |
1132 KB |
Output is correct |
| 27 |
Correct |
61 ms |
1276 KB |
Output is correct |
| 28 |
Correct |
68 ms |
1132 KB |
Output is correct |
| 29 |
Correct |
63 ms |
1132 KB |
Output is correct |
| 30 |
Correct |
42 ms |
1388 KB |
Output is correct |
| 31 |
Correct |
1 ms |
380 KB |
Output is correct |
| 32 |
Correct |
1 ms |
364 KB |
Output is correct |
