Submission #1216571

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216571		tapilyoca	Ancient Books (IOI17_books)	C++20	50 / 100	1705 ms	27856 KiB

books

#include "books.h"
#include <bits/stdc++.h>
using namespace std;

template<typename T>
using vec = vector<T>;
using ll = long long;
using vll = vec<ll>;
using pll = pair<ll,ll>;
#define pb push_back
#define dbg(x) cerr << #x << ": " << x << endl


ll minimum_walk(std::vector<int> p, int s) {
    assert(s == 0);
    ll n = p.size();

    ll ans = 0;
    for(int i = 0; i < n; i++) {
        ans += abs(i-p[i]);
    }

    if(ans == 0) return ans;

    ll cid = 0;
    vll id(n,-1);
    for(int i = 0; i < n; i++) {
        if(id[i] != -1) continue;
        ll at = i;
        id[i] = ++cid;
        do {
            at = p[at];
            id[at] = cid;
        } while(at != i);
    }

    vll last_book(cid+1,-1);
    for(ll i = 0; i < n; i++) {
        last_book[id[i]] = max(last_book[id[i]],i);
    }

    ll last_unsorted = n-1;
    for(ll i = n-1; i >= 0; i--) {
        if(p[i] != i) {
            last_unsorted = i;
            break;
        }
    }

    ll nextFlag = last_book[id[0]];
    for(int i = 0; i <= last_unsorted; i++) {
        if(i <= nextFlag) {
            nextFlag = max(nextFlag, last_book[id[i]]);
        } else {
            dbg(i);
            ans += 2;
            nextFlag = last_book[id[i]];
        }
    }

    // dbg(cid);
    // for(int i = 0; i < n; i++) {
    //     cerr << id[i] << " ";
    // } cerr << endl;

    return ans;
}

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