Submission #790518

#	Time	Username	Problem	Language	Result	Execution time	Memory
790518		skittles1412	Ancient Books (IOI17_books)	C++17	12 / 100	2080 ms	1048576 KiB

books

#include "bits/extc++.h"

using namespace std;

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t;
    ((cerr << " | " << u), ...);
    cerr << endl;
}

#ifdef DEBUG
#define dbg(...)                                              \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: "; \
    dbgh(__VA_ARGS__)
#else
#define dbg(...)
#define cerr   \
    if (false) \
    cerr
#endif

using ll = long long;

#define endl "\n"
#define long int64_t
#define sz(x) int(std::size(x))

struct State {
    vector<int> arr;
    int mpos, mbook;

    bool operator<(const State& s) const {
        return tie(arr, mpos, mbook) < tie(s.arr, s.mpos, s.mbook);
    }
};

ll minimum_walk(vector<int> arr, int kv) {
    int n = sz(arr);

    set<State> vis;
    queue<pair<int, State>> q;

    auto push = [&](const State& u, int d) -> void {
        if (!vis.insert(u).second) {
            return;
        }
        q.emplace(d, u);
    };

    push({arr, kv, -1}, 0);

    while (sz(q)) {
        auto [d, u] = q.front();
        q.pop();
        if (is_sorted(begin(u.arr), end(u.arr)) && u.mbook == -1 &&
            u.mpos == kv) {
            return d;
        }

        for (int du : {-1, 1}) {
            int npos = u.mpos + du;
            if (!(0 <= npos && npos < n)) {
                continue;
            }
            push({u.arr, npos, u.mbook}, d + 1);
        }

        swap(u.arr[u.mpos], u.mbook);
        push(u, d);
    }

    assert(false);
}

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