Submission #566451

#TimeUsernameProblemLanguageResultExecution timeMemory
566451sofapudenAncient Books (IOI17_books)C++14
100 / 100
183 ms34804 KiB
#include "books.h" #include<bits/stdc++.h> using namespace std; typedef long long ll; vector<pair<int,int>> segs; vector<int> vis; pair<int,int> getNext(int x, bool r){ pair<int,int> bound = {x, x}; if(r) { for(int i = x; i <= bound.second; ++i){ bound.first = min(bound.first,segs[vis[i]].first); bound.second = max(bound.second,segs[vis[i]].second); } } else { for(int i = x; i >= bound.first; --i){ bound.first = min(bound.first,segs[vis[i]].first); bound.second = max(bound.second,segs[vis[i]].second); } } return bound; } ll minimum_walk(vector<int> p, int s) { int n = p.size(), mx = 0, cn = 0; ll ans = 0; segs.resize(n+1,{n,0}); vis.resize(n,0); for(int i = 0; i < n; ++i) { if(!vis[i]) { cn++; while(!vis[i]) { ans+=abs(i-p[i]); vis[i] = cn; i = p[i]; // goes back to original i } } } for(int i = 0; i < n; ++i) { segs[vis[i]].first = min(segs[vis[i]].first,i); segs[vis[i]].second = max(segs[vis[i]].second,i); } queue<int> Q; Q.push(s); int l = s, r = s; while(Q.size()){ auto x = Q.front(); Q.pop(); for(int i = segs[vis[x]].first; i < l; ++i){ Q.push(i); } for(int i = segs[vis[x]].second; i > r; --i){ Q.push(i); } l = min(l,segs[vis[x]].first); r = max(r,segs[vis[x]].second); } int cnt = 0; int cua = 0, cub = 0; while(l || r < n-1){ cnt++; pair<int,int> a = {r,r}, b = {l,l}; if(r < n-1)a = getNext(r+1,1); if(l)b = getNext(l-1,0); if(a.first == a.second)cua++; else cua = 0; if(b.first == b.second)cub++; else cub = 0; if(a.first <= b.second){ ans+=2*cnt; cnt = 0; cua = cub = 0; } pair<int,int> nbound = {min(a.first,b.first),max(a.second,b.second)}; for(int i = nbound.first; i < l; ++i){ Q.push(i); } for(int i = nbound.second; i > r; --i){ Q.push(i); } while(Q.size()){ auto x = Q.front(); Q.pop(); for(int i = segs[vis[x]].first; i < l; ++i){ Q.push(i); } for(int i = segs[vis[x]].second; i > r; --i){ Q.push(i); } l = min(l,segs[vis[x]].first); r = max(r,segs[vis[x]].second); } } ans+=4*cnt-2*(cua+cub); return ans; }

Compilation message (stderr)

books.cpp: In function 'll minimum_walk(std::vector<int>, int)':
books.cpp:28:20: warning: unused variable 'mx' [-Wunused-variable]
   28 |  int n = p.size(), mx = 0, cn = 0;
      |                    ^~
#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...