Submission #429045

#	Time	Username	Problem	Language	Result	Execution time	Memory
429045		Dremix10	Ancient Books (IOI17_books)	C++17	50 / 100	164 ms	19736 KiB

books

#include "books.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
#define endl '\n'
#define F first
#define S second
#define all(x) (x).begin(),(x).end()
const int N = 3e5+1;
const ll INF = 2e18;
const int MOD = 1e9+7;


long long minimum_walk(vector<int> p, int s) {
    int i,n = p.size();

    ll ans = 0;
    bool ok[n] = {};
    int r[n];
    int cnt = 0;

    for(i=0;i<n;i++){
        if(p[i] == i){
            ok[i] = true;
            cnt++;
        }
        r[i] = -1;
    }

    i = 0;

    while(cnt < n){
        while(ok[i]){
            i++;
            //ans++;
        }
        int fin = i;
        ans += abs(p[i] - i);
        i = p[i];
        ok[i] = true;
        cnt++;
        while(i != fin){
            r[fin] = max(r[fin],i);
            ans += abs(p[i] - i);
            i = p[i];
            ok[i] = true;
            cnt++;
        }
        //cout<<cnt<<" "<<ans<<" "<<i<<endl;
    }

    int border = 0;
    for(i=0;i<n;i++){
        if(r[i] == -1)continue;
        ans += max(0,i-border)*2;
        border = max(border,r[i]);
    }

    return ans;
}

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