제출 #216007

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
216007		emil_physmath	고대 책들 (IOI17_books)	C++17	0 / 100	7 ms	384 KiB

books

#include "books.h"
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;

long long minimum_walk(vector<int> a, int s)
{
    int n = a.size();
    long long ans = 0;
    vector<bool> used(n);
    vector<pair<int, int> > p;
    for (int i = 0; i < n; ++i)
        if (!used[i])
        {
            int j = i;
            p.push_back({i, i});
            do {
                used[j] = true;
                j = a[j];
                p.back().second = max(p.back().second, j);
            } while(j != i);
        }
    sort(p.begin(), p.end());
    int r = 0;
    for (pair<int, int>& x: p)
        if (x.first <= r)
            r = max(r, x.second);
        else
        {
            ans += 2 * (x.first - r);
            // ans = max(ans, 2LL * x.first);
            r = x.second;
        }
    for (int i = 0; i < n; ++i)
        ans += abs(a[i] - i);
    return ans;
}

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