제출 #1074796

#제출 시각아이디문제언어결과실행 시간메모리
1074796ArthuroWich고대 책들 (IOI17_books)C++17
70 / 100
2059 ms53996 KiB
#include "books.h" #include<bits/stdc++.h> using namespace std; int n, minl, maxr; vector<int> pref, f1, f2; vector<pair<int, int>> cyc; map<pair<int, int>, int> dp; pair<int, int> getrange(int l, int r) { int lv, rv; lv = min(l, min(cyc[l].first, cyc[r].first)); rv = max(r, max(cyc[l].second, cyc[r].second)); while(lv < l || r < rv) { if (lv < l) { l--; lv = min(lv, cyc[l].first); rv = max(rv, cyc[l].second); } else { r++; lv = min(lv, cyc[r].first); rv = max(rv, cyc[r].second); } } return {l, r}; } int calc(int l, int r) { pair<int, int> lrange; lrange = getrange(l, r); l = lrange.first; r = lrange.second; if (dp.find({l, r}) != dp.end()) { return dp[{l, r}]; } if (l-1 < minl && r+1 > maxr) { dp[{l, r}] = 0; return 0; } if (l-1 < minl) { dp[{l, r}] = 2+calc(l, r+1); return dp[{l, r}]; } else if (r+1 > maxr) { dp[{l, r}] = 2+calc(l-1, r); return dp[{l, r}]; } else { dp[{l, r}] = 2+min(calc(l-1, r), calc(l, r+1)); return dp[{l, r}]; } } long long minimum_walk(vector<int> p, int s) { long long int ans = 0; n = p.size(); pref.resize(n+1, 0); f1.resize(n, 0); f2.resize(n, 0); cyc.resize(n); minl = INT_MAX; maxr = 0; for (int i = 0; i < n; i++) { ans += abs(i-p[i]); } vector<pair<int, int>> cycles; vector<int> vis(n, 0); for (int i = 0; i < n; i++) { if (p[i] == i) { cyc[i] = {i, i}; continue; } if (vis[i]) { continue; } int a = i, l = i, r = i; vis[i] = 1; a = p[i]; vis[a] = 1; l = min(l, a); r = max(r, a); while(a != i) { a = p[a]; vis[a] = 1; l = min(l, a); r = max(r, a); } a = p[a]; cyc[a] = {l, r}; while(a != i) { a = p[a]; cyc[a] = {l, r}; } minl = min(minl, l); maxr = max(maxr, r); cycles.push_back({min(l, r), max(l, r)}); } for (auto [i, j] : cycles) { pref[i] += 1; pref[j] -= 1; } for (int i = 1; i < n; i++) { pref[i] += pref[i-1]; } if (s == 0) { for (int i = n-1; i >= 0; i--) { if (pref[i] > 0) { f2[i] = 1; } if (i < n-1) { f2[i] |= f2[i+1]; } } for (int i = n-1; i >= 0; i--) { if (f2[i] && pref[i] == 0) { ans += 2; } } } else { ans += calc(s, s); } 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...