Submission #1083272

#TimeUsernameProblemLanguageResultExecution timeMemory
1083272Math4Life2020Ancient Books (IOI17_books)C++17
50 / 100
97 ms39508 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using pii = pair<ll,ll>; const ll INF = 1e8; //#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; } for (ll i=0;i<N;i++) { if (p[i]>i) { flux[i]++; flux[p[i]]--; } } 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]); } //ll xc = 0; /*for (ll i=1;i<=N;i++) { //cout << "i="<<i<<", maxl="<<maxl[i]<<", minl="<<minl[i]<<"\n"; if (minl[i]!=INF) { //ans += abs(xc-minl[i]); //xc = minl[i]; //ans += abs(xc-maxl[i]); //xc = maxl[i]; ans += 2*(maxl[i]-minl[i]); if (i==1) { if (s<minl[i]) { ans += 2*(minl[i]-s); } else if (s>maxl[i]) { ans += 2*(maxl[i]-s); } } } }*/ if (minl[1]!=INF) { //valid if s=0 ans += 2*(maxl[1]-minl[1]); /*if (s<minl[1]) { ans += 2*(minl[1]-s); } else if (s>maxl[1]) { ans += 2*(s-maxl[1]); }*/ ll MD = INF; for (ll i=0;i<N;i++) { if (p[i]!=i) { MD = min(MD,abs(s-i)); } } ans += 2*MD; } //cout << "minl[1],maxl[1]="<<minl[1]<<","<<maxl[1]<<"\n"; //ans += abs(xc); return ans; } /*int main() { vector<int> p1 = {0,1,4,3,2,5,6}; cout << minimum_walk(p1,3); }*/
#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...