제출 #1083290

#제출 시각아이디문제언어결과실행 시간메모리
1083290Math4Life2020고대 책들 (IOI17_books)C++17
50 / 100
629 ms106612 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using pii = pair<ll,ll>; const ll INF = 1e18; //#include "books.h" ll minimum_walk(vector<int> p, int s) { ll N = p.size(); ll flux[N]; for (ll i=0;i<N;i++) { flux[i]=0; } ll invcnt=0; for (ll i=0;i<N;i++) { if (p[i]>i) { invcnt++; flux[i]++; flux[p[i]]--; } } if (invcnt==0) { return 0; } ll pf[N+1]; pf[0]=0; ll ans = 0; for (ll i=0;i<N;i++) { pf[i+1]=pf[i]+flux[i]; //cout << "x="<<(i+1)<<", pf[x]="<<pf[i+1]<<"\n"; if (pf[i+1]>1) { ans += 2*(pf[i+1]-1); } } ll maxl[N+1]; ll minl[N+1]; for (ll i=0;i<=N;i++) { maxl[i]=-INF; minl[i]=INF; } for (ll i=1;i<=N;i++) { maxl[pf[i]]=max(maxl[pf[i]],i); minl[pf[i]]=min(minl[pf[i]],i-1); } for (ll i=N;i>=1;i--) { maxl[i-1]=max(maxl[i],maxl[i-1]); minl[i-1]=min(minl[i],minl[i-1]); } if (minl[1]!=INF) { //below valid if s=0 ans += 2*(maxl[1]-minl[1]); } if (minl[1]!=INF) { //below valid if s=0 if (s==0) { //ans += 2*(minl[1]); } } if (1) { bool found[N]; ll grp[N]; bool grpf[N]; vector<vector<ll>> gelem; bool foundg[N]; bool found2[N]; for (ll i=0;i<N;i++) { found[i]=0; grp[i]=-1; grpf[i]=0; foundg[i]=0; found2[i]=0; } for (ll i=0;i<N;i++) { if (!found[i]) { vector<ll> enew; //cout << "f1\n"; ll j = i; ll T = 0; ll lp=INF; ll rp=-INF; do { T++; lp = min(lp,j); rp = max(rp,j); found[j]=1; enew.push_back(j); j=p[j]; } while (j != i); for (ll x: enew) { grp[x]=gelem.size(); //cout << "x="<<x<<", grp[x]="<<grp[x]<<"\n"; } gelem.push_back(enew); } } priority_queue<pii> pq; //{-time,position} pq.push({0,s}); ll Tmin = INF; while (!pq.empty()) { auto A = pq.top(); pq.pop(); ll t = -A.first; ll x = A.second; if (found2[x]) { continue; } found2[x]=1; if (x==maxl[1] || x==minl[1]) { Tmin = min(Tmin,t); } ll g = grp[x]; if (!foundg[g]) { foundg[g]=1; for (ll y: gelem[g]) { if (y != x) { pq.push({-t,y}); } } } if (x>0) { pq.push({-t-1,x-1}); } if (x<(N-1)) { pq.push({-t-1,x+1}); } } ans += 2*Tmin; } //cout << "minl[1],maxl[1]="<<minl[1]<<","<<maxl[1]<<"\n"; return ans; } /*int main() { vector<int> p1 = {0,1,4,3,2,5,6}; cout << minimum_walk(p1,3); }*/

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

books.cpp: In function 'll minimum_walk(std::vector<int>, int)':
books.cpp:59:8: warning: variable 'grpf' set but not used [-Wunused-but-set-variable]
   59 |   bool grpf[N];
      |        ^~~~
#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...