Submission #1204919

#TimeUsernameProblemLanguageResultExecution timeMemory
1204919HasanV11010238Ancient Books (IOI17_books)C++20
50 / 100
134 ms19784 KiB
#include "books.h" #include <bits/stdc++.h> #define ll long long using namespace std; vector<int> vis, to, mm; int ri; void dfs(int x){ ri = max(ri, x); vis[x] = 1; if (vis[to[x]] == 0) dfs(to[x]); } void ass(int x, int va){ mm[x] = va; vis[x] = 2; if (vis[to[x]] == 1) ass(to[x], va); } long long minimum_walk(std::vector<int> p, int s) { int n = p.size(); ll ans = 0; for (int i = 0; i < n; i++){ ans += abs(i - p[i]); } to = p; vis.assign(n, 0), mm.assign(n, 0); for (int i = 0; i < n; i++){ if (vis[i] == 0){ ri = 0; dfs(i); ass(i, ri); } } int tt = 0, wh = n - 1; while (to[wh] == wh) wh--; for (int i = 0; i < wh; i++){ if (tt < i) ans += 2; tt = max(tt, mm[i]); } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...