Submission #593976

#	Time	Username	Problem	Language	Result	Execution time	Memory
593976		AlperenT	Ancient Books (IOI17_books)	C++17	12 / 100	2078 ms	1048576 KiB

books

#include <bits/stdc++.h>
#include "books.h"

using namespace std;

const int N = 7, F = 5040, INF = 1e9 + 5;

struct Item{
    vector<int> arr;

    int indx, hold;

    bool operator < (const Item &sc) const{
        if(arr == sc.arr){
            if(indx == sc.indx) return hold < sc.hold;
            else return indx < sc.indx;
        }
        else return arr < sc.arr;
    }
};

map<Item, int> dist;

long long minimum_walk(vector<int> p, int s){
    int n = p.size();

    vector<int> v(n);
    iota(v.begin(), v.end(), 0);

    dist[{p, s, -1}] = 0;

    priority_queue<pair<int, Item>> pq;

    pq.push({0, {p, s, -1}});

    while(!pq.empty()){
        auto v = pq.top().second; pq.pop();

        if(v.indx - 1 >= 0){
            Item nxt = {v.arr, v.indx - 1, v.hold};

            if(dist.find(nxt) == dist.end() || dist[v] + 1 < dist[nxt]){
                dist[nxt] = dist[v] + 1;
                pq.push({-dist[nxt], nxt});
            }
        }

        if(v.indx + 1 < n){
            Item nxt = {v.arr, v.indx + 1, v.hold};

            if(dist.find(nxt) == dist.end() || dist[v] + 1 < dist[nxt]){
                dist[nxt] = dist[v] + 1;
                pq.push({-dist[nxt], nxt});
            }
        }

        if(v.hold == -1){
            if(v.arr[v.indx] != -1){
                Item nxt = {v.arr, v.indx, v.arr[v.indx]};

                nxt.arr[v.indx] = -1;

                if(dist.find(nxt) == dist.end() || dist[v] < dist[nxt]){
                    dist[nxt] = dist[v];
                    pq.push({-dist[nxt], nxt});
                }
            }
        }

        if(v.hold != -1){
            Item nxt = v;

            swap(nxt.arr[nxt.indx], nxt.hold);

            if(dist.find(nxt) == dist.end() || dist[v] < dist[nxt]){
                dist[nxt] = dist[v];
                pq.push({-dist[nxt], nxt});
            }
        }
    }

    vector<int> sorted(n);

    iota(sorted.begin(), sorted.end(), 0);

    return dist[{sorted, s, -1}];
}

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