Submission #1061483

#TimeUsernameProblemLanguageResultExecution timeMemory
1061483ZicrusAncient Books (IOI17_books)C++17
50 / 100
142 ms33280 KiB
#include <bits/stdc++.h> #include "books.h" using namespace std; typedef long long ll; ll minimum_walk(vector<int> p, int s) { ll n = p.size(); ll res = 0; for (int i = 0; i < n; i++) res += abs(p[i] - i); vector<bool> vst(n); vector<vector<ll>> cyc = {{0}}; vector<ll> mxCyc = {0}; for (int i = 0; i < n; i++) { if (vst[i] || p[i] == i) continue; cyc.push_back(vector<ll>()); mxCyc.push_back(i); ll cur = i; do { cyc.back().push_back(cur); mxCyc.back() = max(mxCyc.back(), cur); cur = p[cur]; vst[cur] = true; } while (cur != i); } ll m = cyc.size(); ll mx = 0; for (int i = 1; i < m; i++) { mx = max(mx, mxCyc[i-1]); res += 2*max(0ll, cyc[i][0] - mx); } return res; }
#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...