Submission #1012183

#TimeUsernameProblemLanguageResultExecution timeMemory
1012183hyakupAncient Books (IOI17_books)C++17
50 / 100
82 ms9224 KiB
#include "books.h" #include <bits/stdc++.h> using namespace std; #define bug(x) cout << #x << " " << x << endl; #define ll long long const ll maxn = 1e6 + 10; bool marc[maxn]; long long minimum_walk(vector<int> p, int s) { if( is_sorted( p.begin(), p.end() ) ) return 0; ll n = (ll)p.size(); ll resp = 0; for( ll i = 0; i < (ll)p.size(); i++ ) resp += (ll)abs(p[i] - i); ll maxi = -1; bool contido = false; for( ll i = 0; i < n; i++ ){ if( !marc[i] && p[i] != i ){ if( maxi != -1 && i > maxi ) resp += 2LL*(i - maxi); ll cur = i; while( !marc[cur] ){ maxi = max( maxi, cur ); marc[cur] = true; cur = p[cur]; } if( i <= s && s <= maxi ) contido = true; } } ll l = s, r = s; while( l >= 0 && !marc[l] ) l--; while( r < n && !marc[r] ) r++; if( contido ) resp += 2LL*min( s - l, r - s ); else{ if( l == -1 ) resp += 2LL*(r - s); else if( r == n ) resp += 2LL*(s - l); } return resp; }
#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...