Submission #1261555

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261555		biank	Ancient Books (IOI17_books)	C++20	100 / 100	117 ms	20276 KiB

books

#include "books.h"
#include <bits/stdc++.h>
 
#define forsn(i, s, n) for (int i = int(s); i < int(n); i++)
#define forn(i, n) forsn(i, 0, n)
#define dforsn(i, s, n) for (int i = int(n) - 1; i >= int(s); i--)
#define dforn(i, n) dforsn(i, 0, n)
 
#define sz(x) int(x.size())
#define all(x) begin(x), end(x)
 
#define pb push_back
#define eb emplace_back
 
#define fst first
#define snd second
 
using namespace std;
 
using vi = vector<int>;
using ii = pair<int, int>;
using ll = long long;

ll minimum_walk(vi p, int s) {
    const int n = sz(p);
    vi L, R;
    vi cycle(n);
    vector<bool> vis(n, false);
    forn(i, n) {
        if (vis[i]) continue;
        int j = i, l = i, r = i;
        while (!vis[j]) {
            vis[j] = true;
            cycle[j] = sz(L);
            l = min(l, j);
            r = max(r, j);
            j = p[j];
        }
        L.pb(l), R.pb(r);
    }
    const int c = sz(L);
    ll ret = 0;
    forn(i, n) ret += abs(i - p[i]);
    int needL = s, needR = s;
    forn(i, c) {
        if (L[i] == R[i]) continue;
        needL = min(needL, L[i]);
        needR = max(needR, R[i]);
    }
    auto extend = [&](int &l, int &r) {
        int newL = l;
        int newR = r;
        auto update = [&](int id) {
            newL = min(newL, L[id]);
            newR = max(newR, R[id]);
        };
        update(cycle[l]);
        update(cycle[r]);
        while (newL < l || newR > r) {
            if (newL < l) update(cycle[--l]);                
            if (newR > r) update(cycle[++r]);
        }
    };
    int l = s, r = s;
    extend(l, r);
    while (l > needL || r < needR) {
        int leftCost = 0, rightCost = 0;
        bool flag = false;
        int newL = l, newR = r;
        while (newL > needL && newR == r) {
            newL--; extend(newL, newR);
            leftCost += 2;
        }
        flag = newR > r;
        int nextL = newL, nextR = newR;
        newL = l, newR = r;
        while (newR < needR && newL == l) {
            newR++; extend(newL, newR);
            rightCost += 2;
        }
        nextL = min(nextL, newL);
        nextR = max(nextR, newR);
        assert(flag == (newL < l));
        if (flag) {
            ret += min(leftCost, rightCost);
        } else {
            ret += leftCost + rightCost;
        }
        l = nextL, r = nextR;
        extend(l, r);
    }
    return ret;
}

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