Submission #40337

#	Time	Username	Problem	Language	Result	Execution time	Memory
40337		jackyliuxx	Ancient Books (IOI17_books)	C++14	100 / 100	315 ms	21528 KiB

books

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

vector<int> group;
vector<int> group_head, group_tail;

int find_group(int x) {
    return x == group[x] ? x : group[x] = find_group(group[x]);
}

void merge_group(int x, int y) {
    int gx = find_group(x), gy = find_group(y);
    group_head[gx] = min(group_head[gx], group_head[gy]);
    group_tail[gx] = max(group_tail[gx], group_tail[gy]);
    group[gy] = gx;
}

bool is_head(int x) {
    return group_head[find_group(x)] == x;
}

bool is_tail(int x) {
    return group_tail[find_group(x)] == x;
}

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

    group.assign(n, 0);
    group_head.assign(n, 0);
    group_tail.assign(n, 0);

    for (int i = 0; i < n; i++) {
        group[i] = i;
        group_head[i] = i;
        group_tail[i] = i;
    }

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

    stack<int> stk;
    for (int i = 0; i < n; i++) {
        if (is_head(i)) {
            stk.push(i);
        } else {
            while (find_group(stk.top()) != find_group(i)) {
                merge_group(stk.top(), i);
                stk.pop();
            }
        }
        if (is_tail(i)) {
            stk.pop();
        }
    }

    int target_head = 0, target_tail = n - 1;
    for (int i = 0; i < n && p[i] == i; i++) {
        target_head++;
    }
    for (int i = n - 1; i > 0 && p[i] == i; i--) {
        target_tail--;
    }

    int g = find_group(s);
    int head = group_head[g], tail = group_tail[g];
    while (head > target_head || tail < target_tail) {
        int l = head, ld = 0;
        while (l > target_head) {
            l--;
            ld++;
            int lg = find_group(l);
            l = group_head[lg];
            if (group_tail[lg] > tail) {
                break;
            }
        }
        int r = tail, rd = 0;
        while (r < target_tail) {
            r++;
            rd++;
            int rg = find_group(r);
            r = group_tail[rg];
            if (group_head[rg] < head) {
                break;
            }
        }
        if (find_group(l) == find_group(r)) {
            g = find_group(l);
            head = group_head[g];
            tail = group_tail[g];
            ans += min(ld, rd) * 2;
        } else {
            head = l;
            tail = r;
            ans += ld * 2;
            ans += rd * 2;
        }
    }

	return ans;
}

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