제출 #1147999

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1147999		raphaelp	고대 책들 (IOI17_books)	C++20	12 / 100	0 ms	328 KiB

books

#include <bits/stdc++.h>
#include "books.h"
using namespace std;
int find(int x, vector<int> &p)
{
    return (x == p[x]) ? x : p[x] = find(p[x], p);
}
void search(int x, vector<int> &group, vector<int> &L, vector<int> &R, vector<int> &occ, vector<int> &P, vector<int> &Tab, int &cur)
{
    occ[x] = 1;
    int until = R[x];
    while (cur <= until)
    {
        if (find(group[Tab[cur]], P) == find(x, P))
        {
            cur++;
            continue;
        }
        if (R[find(group[Tab[cur]], P)] > until)
        {
            R[find(x, P)] = max(R[find(x, P)], R[find(group[Tab[cur]], P)]);
            L[find(x, P)] = min(L[find(x, P)], L[find(group[Tab[cur]], P)]);
            P[find(group[Tab[cur]], P)] = find(x, P);
            until = R[find(x, P)];
            cur++;
        }
        else
        {
            search(group[Tab[cur]], group, L, R, occ, P, Tab, cur);
        }
    }
}
long long minimum_walk(vector<int> p, int s)
{
    int N = p.size();
    long long ans = 0;
    vector<int> group(N), occ(N), L, R, P;
    int buff = 0;
    for (int i = 0; i < N; i++)
    {
        if (occ[i])
            continue;
        P.push_back(buff);
        int x = i;
        occ[x] = 1;
        group[x] = buff;
        ans += abs(p[x] - x);
        x = p[x];
        L.push_back(i);
        int maxx = i;
        while (x != i)
        {
            maxx = max(maxx, x);
            occ[x] = 1;
            group[x] = buff;
            ans += abs(p[x] - x);
            x = p[x];
        }
        R.push_back(maxx);
        buff++;
    }
    occ.assign(buff, 0);
    int cur = 0;
    for (int i = 0; i < N; i++)
    {
        if (occ[find(group[i], P)])
            continue;
        search(group[i], group, L, R, occ, P, p, cur);
    }
    for (int i = 0; i < N; i++)
        group[i] = find(group[i], P);
    int pos = L[group[s]];
    int l = 0, r = N - 1;
    while (l < N && p[l] == l)
        l++;
    while (r >= 0 && p[r] == r)
        r--;
    while (pos > l)
    {
        ans += 2;
        pos = L[group[pos - 1]];
    }
    pos = R[group[s]];
    while (pos < r)
    {
        ans += 2;
        pos = R[group[pos + 1]];
    }
    return ans;
}

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