Submission #601113

#TimeUsernameProblemLanguageResultExecution timeMemory
601113LucppAncient Books (IOI17_books)C++17
100 / 100
148 ms22924 KiB
#include "books.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; long long minimum_walk(vector<int> p, int s){ int n = (int)p.size(); ll ans = 0; vector<int> cycle(n, -1); vector<int> cmi, cma; int numCycles = 0; for(int i = 0; i < n; i++){ if(cycle[i] == -1 && p[i] != i){ int mi = i, ma = i; int j = i; do { mi = min(mi, j); ma = max(ma, j); cycle[j] = numCycles; ans += abs(j-p[j]); j = p[j]; }while(j != i); numCycles++; cmi.push_back(mi); cma.push_back(ma); } } int mi = s, ma = s; int l = s, r = s; vector<bool> vis(numCycles); bool over = true; while(true){ int i = -1; while(r <= ma){ if(cycle[r] != -1 && !vis[cycle[r]]){ i = r; break; } else r++; } if(i == -1) while(l >= mi){ if(cycle[l] != -1 && !vis[cycle[l]]){ i = l; break; } else l--; } if(i == -1 && over){ int costL = 0, costR = 0; int candL = -1, candR = -1; int until = mi; for(int j = l; j >= 0; j--){ if(j < until) costL += 2; if(cycle[j] != -1){ until = min(until, cmi[cycle[j]]); if(cma[cycle[j]] > ma){ candL = j; break; } } } until = ma; for(int j = r; j < n; j++){ if(j > until) costR += 2; if(cycle[j] != -1){ until = max(until, cma[cycle[j]]); if(cmi[cycle[j]] < mi){ candR = j; break; } } } if(costL < costR) i = candL; else i = candR; if(i != -1) ans += min(costL, costR); if(i == -1) over = false; } if(i == -1){ int oldR = r, oldL = l; while(r < n){ if(cycle[r] != -1 && !vis[cycle[r]]){ i = r; ans += 2*(r+1-oldR); break; } r++; } if(i == -1) while(l >= 0){ if(cycle[l] != -1 && !vis[cycle[l]]){ i = l; ans += 2*(oldL+1-l); break; } l--; } } if(i == -1) break; vis[cycle[i]] = true; mi = min(mi, cmi[cycle[i]]); ma = max(ma, cma[cycle[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...