Submission #1261579

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261579		biank	Ancient Books (IOI17_books)	C++20	100 / 100	126 ms	20560 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 = array<int, 2>;
using ll = long long;

void unite(ii &a, ii b) {
    a[0] = min(a[0], b[0]), a[1] = max(a[1], b[1]);
}

ll minimum_walk(vi p, int s) {
    const int n = sz(p);
    vector<ii> range;
    vi cycle(n);
    vector<bool> vis(n, false);
    forn(i, n) {
        if (vis[i]) continue;
        int j = i;
        ii currRange = {j, j};
        while (!vis[j]) {
            vis[j] = true;
            cycle[j] = sz(range);
            unite(currRange, ii{j, j});
            j = p[j];
        }
        range.pb(currRange);
    }
    const int c = sz(range);
    ll ret = 0;
    forn(i, n) ret += abs(i - p[i]);
    ii need = {s, s};
    forn(i, c) {
        if (range[i][0] == range[i][1]) continue;
        unite(need, range[i]);
    }
    const ii diff = {-1, 1};
    auto extend = [&](ii &currRange) {
        ii newRange = currRange;
        forn(t, 2) unite(newRange, range[cycle[currRange[t]]]);
        while (currRange != newRange) {
            forn(t, 2) if (newRange[t] != currRange[t]) {
                currRange[t] += diff[t];
                unite(newRange, range[cycle[currRange[t]]]);
            }          
        }
    };
    ii currRange = {s, s};
    extend(currRange);
    while (currRange[0] > need[0] || currRange[1] < need[1]) {
        ii cost = {0, 0};
        bool flag[2] = {false, false};
        ii nextRange = currRange;
        forn(t, 2) {
            ii newRange = currRange;
            while (newRange[t] * diff[t] < need[t] * diff[t] && newRange[1 - t] == currRange[1 - t]) {
                newRange[t] += diff[t]; extend(newRange); cost[t] += 2;
            }
            flag[t] = !(newRange[1 - t] == currRange[1 - t]);
            unite(nextRange, newRange);
        }
        assert(flag[0] == flag[1]);
        if (flag[0]) ret += min(cost[0], cost[1]);
        else ret += cost[0] + cost[1];
        currRange = nextRange;
        extend(currRange);
    }
    return ret;
}

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