Submission #1083208

#TimeUsernameProblemLanguageResultExecution timeMemory
1083208Math4Life2020Ancient Books (IOI17_books)C++17
0 / 100
1 ms348 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using pii = pair<ll,ll>; const ll INF = 1e8; 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; for (ll i=0;i<N;i++) { pf[i+1]=pf[i]+flux[i]; //cout << "x="<<(i+1)<<", pf[x]="<<pf[i+1]<<"\n"; } 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); } ll xc = 0; ll ans = 0; for (ll i=1;i<=N;i++) { 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]); } } //ans += abs(xc); return ans; } /*int main() { vector<int> p1 = {5,4,3,2,1,0}; cout << minimum_walk(p1,0); }*/

Compilation message (stderr)

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