제출 #566419

#제출 시각아이디문제언어결과실행 시간메모리
566419sofapuden고대 책들 (IOI17_books)C++14
12 / 100
1 ms300 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); } return bound; } 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 cu = 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)cu++; if(b.first == b.second)cu++; if(a.first <= b.second){ ans+=2*cnt; cnt = 0; cu = 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*cu; return ans; }

컴파일 시 표준 에러 (stderr) 메시지

books.cpp: In function 'll minimum_walk(std::vector<int>, int)':
books.cpp:29:20: warning: unused variable 'mx' [-Wunused-variable]
   29 |  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...