| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 389056 |
2021-04-13T14:55:37 Z |
prvocislo |
Gap (APIO16_gap) |
C++17 |
|
109 ms |
7784 KB |
#include "gap.h"
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <iomanip>
typedef long long ll;
using namespace std;
// MinMax(, , &, &);
ll best;
void upd(ll x)
{
best = max(best, x);
}
long long findGap1(int N)
{
ll mini = -1, maxi = 1e18 + 79;
vector<ll> v(N);
for (int l = 0, r = N - 1; l <= r; l++, r--)
{
mini++, maxi--;
MinMax(mini, maxi, &mini, &maxi);
v[l] = mini;
v[r] = maxi;
}
ll ans = 0;
for (int i = 0; i < N - 1; i++) ans = max(ans, v[i + 1] - v[i]);
return ans;
}
long long findGap(int T, int N)
{
if (T == 1)return findGap1(N);
ll mini = -1, maxi = 1e18; best = 1;
set<ll> s;
set<pair<ll, pair<ll, ll> >, greater<pair<ll, pair<ll, ll> >> > pq;
MinMax(mini, maxi, &mini, &maxi);
s.insert({ mini, maxi });
pq.insert({ maxi - mini, {mini, maxi} });
while (!pq.empty())
{
ll dist = pq.begin()->first;
if (dist <= best) return best;
mini = pq.begin()->second.first;
maxi = pq.begin()->second.second;
if (mini + 1 == maxi) break;
if (mini + 2 == maxi)
{
ll a;
MinMax(mini + 1, maxi - 1, &a, &a);
if (a == -1) upd(2);
else upd(1);
break;
}
pq.erase(pq.begin());
ll m1 = (mini + maxi) / 2, m2 = (mini + maxi) / 2 + 1;
ll mi1, mx1, mi2, mx2;
MinMax(mini + 1, m1, &mi1, &mx1);
MinMax(m2, maxi - 1, &mi2, &mx2);
if (mi1 != -1) s.insert(mi1), s.insert(mx1);
if (mi2 != -1) s.insert(mi2), s.insert(mx2);
upd(*next(s.find(mini)) - mini);
upd(maxi - *prev(s.find(maxi)));
if (mx1 != -1 && mi2 != -1) upd(mi2 - mx1);
pq.insert({ mx1 - mi1, {mi1, mx1} });
pq.insert({ mx2 - mi2, {mi2, mx2} });
}
return best;
}
| # |
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 |
0 ms |
200 KB |
Output is correct |
| 8 |
Correct |
1 ms |
200 KB |
Output is correct |
| 9 |
Correct |
1 ms |
256 KB |
Output is correct |
| 10 |
Correct |
1 ms |
240 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 |
456 KB |
Output is correct |
| 14 |
Correct |
1 ms |
328 KB |
Output is correct |
| 15 |
Correct |
1 ms |
328 KB |
Output is correct |
| 16 |
Correct |
11 ms |
712 KB |
Output is correct |
| 17 |
Correct |
11 ms |
628 KB |
Output is correct |
| 18 |
Correct |
12 ms |
680 KB |
Output is correct |
| 19 |
Correct |
12 ms |
600 KB |
Output is correct |
| 20 |
Correct |
9 ms |
584 KB |
Output is correct |
| 21 |
Correct |
44 ms |
1824 KB |
Output is correct |
| 22 |
Correct |
47 ms |
1824 KB |
Output is correct |
| 23 |
Correct |
46 ms |
1856 KB |
Output is correct |
| 24 |
Correct |
59 ms |
1828 KB |
Output is correct |
| 25 |
Correct |
40 ms |
1828 KB |
Output is correct |
| 26 |
Correct |
48 ms |
1820 KB |
Output is correct |
| 27 |
Correct |
44 ms |
1816 KB |
Output is correct |
| 28 |
Correct |
44 ms |
1828 KB |
Output is correct |
| 29 |
Correct |
45 ms |
1804 KB |
Output is correct |
| 30 |
Correct |
36 ms |
1864 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 |
2 ms |
200 KB |
Output is correct |
| 4 |
Correct |
0 ms |
200 KB |
Output is correct |
| 5 |
Partially correct |
1 ms |
200 KB |
Partially correct |
| 6 |
Partially correct |
1 ms |
200 KB |
Partially correct |
| 7 |
Partially correct |
1 ms |
200 KB |
Partially correct |
| 8 |
Partially correct |
1 ms |
200 KB |
Partially correct |
| 9 |
Partially correct |
1 ms |
200 KB |
Partially correct |
| 10 |
Correct |
1 ms |
200 KB |
Output is correct |
| 11 |
Partially correct |
1 ms |
328 KB |
Partially correct |
| 12 |
Partially correct |
2 ms |
328 KB |
Partially correct |
| 13 |
Partially correct |
1 ms |
328 KB |
Partially correct |
| 14 |
Partially correct |
1 ms |
328 KB |
Partially correct |
| 15 |
Partially correct |
2 ms |
328 KB |
Partially correct |
| 16 |
Partially correct |
18 ms |
936 KB |
Partially correct |
| 17 |
Partially correct |
13 ms |
908 KB |
Partially correct |
| 18 |
Partially correct |
12 ms |
968 KB |
Partially correct |
| 19 |
Partially correct |
13 ms |
900 KB |
Partially correct |
| 20 |
Correct |
5 ms |
456 KB |
Output is correct |
| 21 |
Partially correct |
53 ms |
3104 KB |
Partially correct |
| 22 |
Partially correct |
53 ms |
3084 KB |
Partially correct |
| 23 |
Partially correct |
55 ms |
3056 KB |
Partially correct |
| 24 |
Partially correct |
52 ms |
3108 KB |
Partially correct |
| 25 |
Partially correct |
109 ms |
7784 KB |
Partially correct |
| 26 |
Partially correct |
57 ms |
3072 KB |
Partially correct |
| 27 |
Partially correct |
53 ms |
3104 KB |
Partially correct |
| 28 |
Partially correct |
53 ms |
3136 KB |
Partially correct |
| 29 |
Partially correct |
57 ms |
3104 KB |
Partially correct |
| 30 |
Correct |
13 ms |
980 KB |
Output is correct |
| 31 |
Correct |
1 ms |
200 KB |
Output is correct |
| 32 |
Correct |
1 ms |
272 KB |
Output is correct |
