Submission #526339

#	Time	Username	Problem	Language	Result	Execution time	Memory
526339		leaked	Ancient Books (IOI17_books)	C++14	50 / 100	165 ms	26824 KiB

books

#include "books.h"
#include <bits/stdc++.h>


#define f first
#define s second
#define vec vector
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define m_p make_pair
#define sz(x) (int)(x).size()
#define pw(x) (1LL<<(x))
//#define pragma optimize("unroll-loops")
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
template <class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
template <class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
const int N=1e6+1;

long long minimum_walk(std::vector<int> p, int s) {
    int n=sz(p);
    vec<int>used(n,0);
    vec<int>rgt(n,0);
    ll ans=0;
    int rit=0;
    for(int i=0;i<n;i++){
        if(used[i]) continue;
        int j=i;
        vec<int>vc;
        while(!used[j]){
            used[j]=1;
            vc.pb(j);
//            cout<<"HEY "<<p[j]<<' '<<j<<endl;
            ans+=abs(p[j]-j);
//            cout<<"ANS
            j=p[j];
        }
        int mx=*max_element(all(vc));
        for(auto &z : vc){
            rgt[z]=mx;
        }
        if(sz(vc)==1) continue;
//        cout<<"HEY "<<endl;
////        for(auto &z : vc)
//            cout<<z<<' ';
//        cout<<endl;
        if(rit<i){
            ans+=2*(i-rit);
            rit=rgt[i];
        }
        umax(rit,rgt[i]);
    }
	return ans;
}

• Subtask 1: 12 / 12
• Subtask 2: 10 / 10
• Subtask 3: 28 / 28
• Subtask 4: 0 / 20
• Subtask 5: 0 / 30