Submission #1060860

#	Time	Username	Problem	Language	Result	Execution time	Memory
1060860		onbert	Ancient Books (IOI17_books)	C++17	50 / 100	105 ms	28864 KiB

books

#include "books.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1e6 + 5, INF = 1e9;
int vis[maxn];

int minimum_walk(vector<int32_t> p, int32_t s) {
    int n = p.size();
    for (int i=0;i<n;i++) vis[i] = false;
    int ans = 0;
    vector<pair<int,int>> vec;
    for (int i=0;i<n;i++) if (!vis[i]) {
        if (p[i]==i && i==s) {
            vec.push_back({s, s});
        }
        if (p[i]==i) continue;
        int u = i;
        pair<int,int> val = {u, u};
        while (true) {
            vis[u] = 1;
            val.first = min(u, val.first);
            val.second = max(u, val.second);
            int v = p[u];
            ans += abs(v-u);
            if (v==i) break;
            u = v;
        }
        vec.push_back(val);
    }
    int sz = vec.size();
    sort(vec.begin(), vec.end());
    int mx = vec[0].second;
    for (int i=1;i<sz;i++) {
        if (vec[i].first > mx) ans += (vec[i].first - mx)*2;
        mx = max(vec[i].second, mx);
    }
    return ans;
}

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