Submission #482539

#	Time	Username	Problem	Language	Result	Execution time	Memory
482539		two_sides	Ancient Books (IOI17_books)	C++17	50 / 100	146 ms	19824 KiB

books

#include "books.h"
#include <bits/stdc++.h>

using namespace std;

template <class X, class Y>
bool cmin(X &a, const  Y &b) {
    return a > b ? a = b, 1 : 0;
}

template <class X, class Y>
bool cmax(X &a, const Y &b) {
    return a < b ? a = b, 1 : 0;
}

long long minimum_walk(vector<int> p, int s) {
    int n = p.size(), cnt = 0;
    long long res = 0;
    vector<int> idx(n, -1), lef(n), rig(n);
    int min_l = s, max_r = s;
    for (int i = 0; i < n; i++) {
        res += abs(p[i] - i);
        if (idx[i] >= 0) continue;
        lef[cnt] = rig[cnt] = i;
        int j = i;
        while (idx[j] < 0) {
            idx[j] = cnt;
            cmin(lef[cnt], j);
            cmax(rig[cnt], j);
            j = p[j];
        }
        cnt++;
        if (i != p[i]) {
            cmin(min_l, i);
            cmax(max_r, i);
        }
    }
    auto extend = [&](int &l, int &r) {
        int tmp_l = min(lef[idx[l]], lef[idx[r]]);
        int tmp_r = max(rig[idx[l]], rig[idx[r]]);
        while (l > tmp_l || r < tmp_r) {
            if (l > tmp_l)
                cmin(tmp_l, lef[idx[l--]]);
            if (r < tmp_r)
                cmax(tmp_r, rig[idx[r++]]);
        }
    };
    int cur_l = s, cur_r = s;
    for (int i = 0; i < n; i++)
        if (i != p[i]) {
            cmin(min_l, i);
            cmax(max_r, i);
        }
    while (cur_l > min_l || cur_r < max_r) {
        extend(cur_l, cur_r);
        bool flag = false;
        int lef_l = cur_l, lef_r = cur_r;
        int cost_l = 0, cost_r = 0;
        while (lef_l > min_l) {
            extend(--lef_l, lef_r);
            cost_l += 2;
            if (lef_r > cur_r) {
                flag = true; break;
            }
        }
        int rig_l= cur_l, rig_r = cur_r;
        while (rig_r < max_r) {
            extend(rig_l, ++rig_r);
            cost_r += 2;
            if (rig_l < cur_l) break;
        }
        if (!flag) res += cost_l + cost_r;
        else res += min(cost_l, cost_r);
        cur_l = min(lef_l, rig_l);
        cur_r = max(lef_r, rig_r);
    }
    return res;
}

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