#include "books.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define ff first
#define ss second
#define pb push_back
long long st123(vector<int> p, int s) {
vector<int> ori = p;
int n = (int)(p.size());
ll ans = 0;
for (int i = 0; i < n; i++) {
if (p[i] == -1 || p[i] == i) continue;
int cur = i;
vector<int> seq = {cur};
while (p[cur] != i) {
cur = p[cur];
seq.pb(cur);
}
// cerr << i << ": ";
// for (int x : seq) cerr << x << ' ';
// cerr << endl;
for (int i = 0; i < (int)(seq.size()); i++) {
ans += abs(seq[(i + 1) % (int)(seq.size())] - seq[i]);
p[seq[i]] = -1;
}
}
vector<int> bruh;
int maxi = 0;
for (int i = 0; i < n; i++) {
maxi = max(maxi, ori[i]);
if (maxi == i) bruh.pb(i);
}
// for (int x : bruh) cerr << x << ' ';
// cerr << endl;
while (bruh.size() >= 2) {
int x = bruh.size();
if (bruh[x - 1] - bruh[x - 2] == 1) {
bruh.pop_back();
} else break;
}
ans += ((int)(bruh.size()) - 1) * 2;
return ans;
}
long long minimum_walk(vector<int> p, int s) {
// if (s == 0) return st123(p, s);
vector<int> ori = p;
int n = (int)(p.size());
ll ans = 0;
vector<pii> range(n);
for (int i = 0; i < n; i++) {
if (p[i] == -1) continue;
int cur = i;
vector<int> seq = {cur};
while (p[cur] != i) {
cur = p[cur];
seq.pb(cur);
}
pii get = {i, i};
for (int x : seq) {
get.ff = min(get.ff, x);
get.ss = max(get.ss, x);
}
// cerr << "seq: ";
// for (int x : seq) cerr << x << ' ';
// cerr << " | " << get.ff << ' ' << get.ss << endl;
for (int j = 0; j < (int)(seq.size()); j++) {
ans += abs(seq[(j + 1) % (int)(seq.size())] - seq[j]);
range[seq[j]] = get;
p[seq[j]] = -1;
}
}
// for (int i = 0; i < n; i++) {
// cerr << i << ": " << range[i].ff << ' ' << range[i].ss << endl;
// }
vector<vector<int>> dp(n);
for (int i = 0; i < n; i++) dp[i].resize(n, 1e9);
deque<pii> dq;
for (int i = range[s].ff; i <= range[s].ss; i++) {
for (int j = i; j <= range[s].ss; j++) {
dp[i][j] = 0;
dq.push_back({i, j});
}
}
while (!dq.empty()) {
pii cur = dq.front(); dq.pop_front();
if (cur.ff > 0) {
pii nrange = {range[cur.ff - 1].ff, max(cur.ss, range[cur.ff - 1].ss)};
if (dp[nrange.ff][nrange.ss] > dp[cur.ff][cur.ss] + 1) {
dp[nrange.ff][nrange.ss] = dp[cur.ff][cur.ss] + 1;
dq.push_back(nrange);
}
}
if (cur.ff < n - 1) {
pii nrange = {cur.ff + 1, cur.ss};
if (dp[nrange.ff][nrange.ss] > dp[cur.ff][cur.ss]) {
dp[nrange.ff][nrange.ss] = dp[cur.ff][cur.ss];
dq.push_front(nrange);
}
}
if (cur.ss < n - 1) {
pii nrange = {min(cur.ff, range[cur.ss + 1].ff), range[cur.ss + 1].ss};
if (dp[nrange.ff][nrange.ss] > dp[cur.ff][cur.ss] + 1) {
dp[nrange.ff][nrange.ss] = dp[cur.ff][cur.ss] + 1;
dq.push_back(nrange);
}
}
if (cur.ss > 0) {
pii nrange = {cur.ff, cur.ss - 1};
if (dp[nrange.ff][nrange.ss] > dp[cur.ff][cur.ss]) {
dp[nrange.ff][nrange.ss] = dp[cur.ff][cur.ss];
dq.push_front(nrange);
}
}
}
int lb = 0, rb = n - 1;
while (lb < n && ori[lb] == lb) lb++;
if (lb == n) return 0;
while (rb >= 0 && ori[rb] == rb) rb--;
ans += dp[lb][rb] * 2;
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
348 KB |
Output is correct |
| 6 |
Correct |
1 ms |
344 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
348 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Correct |
0 ms |
432 KB |
Output is correct |
| 11 |
Correct |
1 ms |
604 KB |
Output is correct |
| 12 |
Correct |
0 ms |
348 KB |
Output is correct |
| 13 |
Correct |
0 ms |
348 KB |
Output is correct |
| 14 |
Correct |
0 ms |
348 KB |
Output is correct |
| 15 |
Correct |
0 ms |
348 KB |
Output is correct |
| 16 |
Correct |
1 ms |
348 KB |
Output is correct |
| 17 |
Correct |
0 ms |
344 KB |
Output is correct |
| 18 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
348 KB |
Output is correct |
| 6 |
Correct |
1 ms |
344 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
348 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Correct |
0 ms |
432 KB |
Output is correct |
| 11 |
Correct |
1 ms |
604 KB |
Output is correct |
| 12 |
Correct |
0 ms |
348 KB |
Output is correct |
| 13 |
Correct |
0 ms |
348 KB |
Output is correct |
| 14 |
Correct |
0 ms |
348 KB |
Output is correct |
| 15 |
Correct |
0 ms |
348 KB |
Output is correct |
| 16 |
Correct |
1 ms |
348 KB |
Output is correct |
| 17 |
Correct |
0 ms |
344 KB |
Output is correct |
| 18 |
Correct |
0 ms |
348 KB |
Output is correct |
| 19 |
Incorrect |
19 ms |
8284 KB |
3rd lines differ - on the 1st token, expected: '338572', found: '338574' |
| 20 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
348 KB |
Output is correct |
| 6 |
Correct |
1 ms |
344 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
348 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Correct |
0 ms |
432 KB |
Output is correct |
| 11 |
Correct |
1 ms |
604 KB |
Output is correct |
| 12 |
Correct |
0 ms |
348 KB |
Output is correct |
| 13 |
Correct |
0 ms |
348 KB |
Output is correct |
| 14 |
Correct |
0 ms |
348 KB |
Output is correct |
| 15 |
Correct |
0 ms |
348 KB |
Output is correct |
| 16 |
Correct |
1 ms |
348 KB |
Output is correct |
| 17 |
Correct |
0 ms |
344 KB |
Output is correct |
| 18 |
Correct |
0 ms |
348 KB |
Output is correct |
| 19 |
Incorrect |
19 ms |
8284 KB |
3rd lines differ - on the 1st token, expected: '338572', found: '338574' |
| 20 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
26 ms |
7256 KB |
3rd lines differ - on the 1st token, expected: '3304', found: '2746' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
348 KB |
Output is correct |
| 6 |
Correct |
1 ms |
344 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
348 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Correct |
0 ms |
432 KB |
Output is correct |
| 11 |
Correct |
1 ms |
604 KB |
Output is correct |
| 12 |
Correct |
0 ms |
348 KB |
Output is correct |
| 13 |
Correct |
0 ms |
348 KB |
Output is correct |
| 14 |
Correct |
0 ms |
348 KB |
Output is correct |
| 15 |
Correct |
0 ms |
348 KB |
Output is correct |
| 16 |
Correct |
1 ms |
348 KB |
Output is correct |
| 17 |
Correct |
0 ms |
344 KB |
Output is correct |
| 18 |
Correct |
0 ms |
348 KB |
Output is correct |
| 19 |
Incorrect |
19 ms |
8284 KB |
3rd lines differ - on the 1st token, expected: '338572', found: '338574' |
| 20 |
Halted |
0 ms |
0 KB |
- |
