Submission #270857

#TimeUsernameProblemLanguageResultExecution timeMemory
270857hamerinAncient Books (IOI17_books)C++17
50 / 100
1315 ms160948 KiB
#include "books.h" #include <bits/stdc++.h> #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") using namespace std; using i64 = long long; using d64 = long double; using pi = pair<int, int>; using pli = pair<i64, i64>; using ti = tuple<int, int, int>; using tli = tuple<i64, i64, i64>; #define iterall(cont) cont.begin(), cont.end() #define prec(n) setprecision(n) << fixed i64 minimum_walk(vector<int> p, int s) { const int N = p.size(); vector<vector<int>> cycles; vector<set<int>> cyc_st; vector<int> cyc(N); vector<bool> vst(N); for (int i = 0; i < N; i++) { if (vst[i]) continue; cycles.emplace_back(vector<int>()); cyc_st.emplace_back(set<int>()); int cur = i; while (cycles.back().empty() || cur != i) { cycles.back().emplace_back(cur); cyc_st.back().emplace(cur); cyc[cur] = cycles.size() - 1; vst[cur] = true; cur = p[cur]; } } i64 ans = 0; for (int i = 0; i < N; i++) ans += abs(i - p[i]); vector<pi> intervals; for (auto &st : cyc_st) if (st.size() > 1 || *st.begin() == s) intervals.emplace_back(*st.begin(), *prev(st.end())); sort(iterall(intervals)); int M = 0; for (auto [l, r] : intervals) { if (l > M) ans += 2 * (l - M); M = max(r, M); } 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...