Submission #69618

#	Time	Username	Problem	Language	Result	Execution time	Memory
69618		aquablitz11	Ancient Books (IOI17_books)	C++14	0 / 100	3 ms	496 KiB

books

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

using ll = long long;
using pll = pair<ll, ll>;
const ll INF = 1e9;

ll minimum_walk(vector<int> p, int s)
{
    int n = p.size();
    vector<pll> li;
    ll dist = 0;
    for (int i = 0; i < n; ++i) {
        if (p[i] == -1) continue;
        int u = i, cnt = 0;
        ll l = -INF, r = INF;
        do {
            ++cnt;
            if (u <= s) l = max(l, (ll)u);
            if (u >= s) r = min(r, (ll)u);
            int v = p[u];
            dist += abs(u-v);
            p[u] = -1;
            u = v;
        } while (u != i);
        if (cnt > 1)
            li.emplace_back(s-l, r-s);
    }
    sort(li.begin(), li.end());
    ll mx = 0, ans = INF*INF;
    for (int i = li.size()-1; i >= 0; --i) {
        ans = min(ans, li[i].first + mx);
        mx = max(mx, li[i].second);
    }
    ans = min(ans, mx);

	return dist+2*ans;
}

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