Submission #1189306

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189306		anmattroi	Ancient Books (IOI17_books)	C++17	12 / 100	2125 ms	1082348 KiB

books

#include "books.h"
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
using ii = pair<int, int>;

map<vector<int>, int > nho;
map<int, vector<int> > rem;

int kc[120][4][5];

struct node {
    int idx, s, hold;
    node() {}
    node(int _idx, int _s, int _hold) : idx(_idx), s(_s), hold(_hold) {}

    bool operator < (const node &other) const {
        if (idx != other.idx) return idx < other.idx;
        if (s != other.s) return s < other.s;
        return hold < other.hold;
    }
};


/*
4 0
0 2 3 1
*/


long long minimum_walk(vector<int> p, int s) {
    int n = p.size(), cc = 0;
    if (1) {
        vector<int> a(n);
        iota(a.begin(), a.end(), 0);
        do {
            nho[a] = cc;
            rem[cc] = a;
            ++cc;
            for (int i = 0; i < n; i++) {
                int T = a[i];
                a[i] = n;
                nho[a] = cc;
                rem[cc] = a;
                ++cc;
                a[i] = T;
            }
        } while (next_permutation(a.begin(), a.end()));
    }
    for (int i = 0; i < cc; i++) for (int j = 0; j < n; j++) for (int k = 0; k <= n; k++) kc[i][j][k] = INT_MAX;

    set<pair<int, node> > q;

    kc[nho[p]][s][n] = 0;
    q.insert(pair<int, node>{0, node(nho[p], s, n)});
    while (!q.empty()) {
        auto [idx, s, hold] = q.begin()->se; q.erase(q.begin());
        vector<int> cur = rem[idx];

        if (1) {
            vector<int> T = cur;
            T[s] = hold;

            int nex = nho[T];

            if (kc[nex][s][cur[s]] > kc[idx][s][hold]) {
                q.erase(pair<int, node>{kc[nex][s][cur[s]], node(nex, s, cur[s])});
                kc[nex][s][cur[s]] = kc[idx][s][hold];
                q.insert(pair<int, node>{kc[nex][s][cur[s]], node(nex, s, cur[s])});
            }
        }

        for (int i = 0; i < n; i++)
        if (kc[idx][i][hold] > kc[idx][s][hold] + abs(i-s)) {
            q.erase(pair<int, node>{kc[idx][i][hold], node(idx, i, hold)});
            kc[idx][i][hold] = kc[idx][s][hold] + abs(i-s);
            q.insert(pair<int, node>{kc[idx][i][hold], node(idx, i, hold)});
        }
    }
    return kc[0][s][n];
}

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