//Power Of Ninja Go
#include <bits/stdc++.h>
#ifdef atom
#include "grader.cpp"
#else
#include "books.h"
#endif
using namespace std;
typedef long long ll; typedef pair<int, int> ii; typedef vector<int> vi; typedef vector< ii > vii;
#define X first
#define Y second
#define pb push_back
int n;
const int maxn = 1e6+5;
vector<int> p;
int a[maxn], b[maxn];
ll dist[maxn];
bool vis[maxn];
int belong[maxn];
int cnt = 0;
void dfs(int u)
{
if(vis[u]) return;
vis[u] = true;
belong[u] = cnt;
a[cnt] = min(u, a[cnt]);
b[cnt] = max(u, b[cnt]);
dist[cnt] += abs(p[u]-u);
dfs(p[u]);
}
void change(int &l, int &r)
{
int ll = min(l, min(a[belong[l]], a[belong[r]]));
int rr = max(r, max(b[belong[l]], b[belong[r]]));
while(ll< l || r< rr)
{
if(ll< l)
{
l--;
ll = min(ll, a[belong[l]]);
rr = max(rr, b[belong[l]]);
}
else
{
r++;
ll = min(ll, a[belong[r]]);
rr = max(rr, b[belong[r]]);
}
}
}
int solve(int l, int r, int want_l, int want_r)
{
int ret = 0;
do
{
change(l, r);
//cout << l << ' ' << r << endl;
bool to_left = false;
int costL = 0;
int s_l = l, s_r = r;
while(true)
{
if(s_l<= want_l) break;
s_l--;
costL += 2;
change(s_l, s_r);
if(s_r> r)
{
to_left = true;
break;
}
}
//cout << s_l << '?' << s_r << endl;
bool to_right = false;
int costR = 0;
int k_l = l, k_r = r;
while(true)
{
if(s_r>= want_r) break;
k_r++;
costR += 2;
change(k_l, k_r);
if(k_l< l)
{
to_right = true;
break;
}
}
if(to_left && to_right)
{
ret += min(costL, costR);
}
else
{
ret += costL + costR;
}
l = min(s_l, k_l);
r = max(s_r, k_r);
}
while(want_l< l || r< want_r);
return ret;
}
long long minimum_walk(std::vector<int> P, int s)
{
p = P;
n = P.size();
for(int i = 0; i< n; i++) a[i] = 1e9;
int l = s, r = s;
ll res = 0;
for(int i = 0; i< n; i++)
{
if(vis[i]) continue;
dfs(i);
res += dist[cnt];
if(a[cnt] != b[cnt])
{
l = min(l, a[cnt]);
r = max(r, b[cnt]);
}
cnt++;
}
//don't forget when s = 0
return res+solve(s, s, l, r);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
15 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
15 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
15 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
688 KB |
Output is correct |
| 2 |
Correct |
2 ms |
724 KB |
Output is correct |
| 3 |
Correct |
2 ms |
724 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
760 KB |
3rd lines differ - on the 1st token, expected: '2094', found: '2110' |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
15 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
