Submission #137701

#	Time	Username	Problem	Language	Result	Execution time	Memory
137701		ckodser	Ancient Books (IOI17_books)	C++14	50 / 100	228 ms	24952 KiB

books

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

#define ll int
#define pb push_back
#define mp make_pair
#define ld long double
#define F first
#define S second
#define pii pair<ll,ll> 

using namespace :: std;

const ll maxn=1e6+500;
const ll inf=1e9+900;

vector<ll> p;
bool vis[maxn];
ll d[maxn];

ll cnt=0;
ll mxx[maxn];
ll mnn[maxn];




void dfs(ll a){
    if(vis[a])return;
    vis[a]=2;
    d[a]=cnt;
    dfs(p[a]);
}
long long minimum_walk(vector<int> P, int s){
    p=P;
    ll n=p.size();
    long long ans=0;
    ll last=0;
    for(ll i=0;i<n;i++){
	if(!vis[i]){
	    dfs(i);
	    cnt++;
	}
	if(p[i]!=i)last=i;
	ans+=abs(i-p[i]);
    }
    fill(mnn,mnn+maxn,inf);
    fill(mxx,mxx+maxn,0);

    for(ll i=0;i<n;i++){
	mnn[d[i]]=min(mnn[d[i]],i);
	mxx[d[i]]=max(mxx[d[i]],i);
    }
    if(s==0){
	ll t=0;
	for(ll i=0;i<=last;i++){
	    if(t<i){
		ans+=2;
		t=max(t,i);
	    }
	    t=max(t,mxx[d[i]]);
	}
    }
    return ans;
}

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