Submission #862167

#	Time	Username	Problem	Language	Result	Execution time	Memory
862167		vgtcross	Parking (CEOI22_parking)	C++17	10 / 100	9 ms	16476 KiB

Main

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using pii = pair<ll, ll>;

int enc(array<int, 8> &a) {
    int b = 0;
    for (int i : a) b = 5*b + i;
    return b;
}

array<int, 8> dec(int b) {
    array<int, 8> a;
    for (int i = 7; i >= 0; --i) {
        a[i] = b % 5;
        b /= 5;
    }
    return a;
}

void solve() {
    int n, m;
    cin >> n >> m;
    
    array<int, 8> a;
    for (int i = 0; i < 2*m; ++i) cin >> a[i];
    
    vector<bool> vis(4e5, 0);
    vector<int> p(4e5);
    vector<pii> mov(4e5);
    
    int b = enc(a);
    vis[b] = 1;
    p[b] = -1;
    queue<int> bfs;
    bfs.push(b);
    while (bfs.size()) {
        b = bfs.front();
        bfs.pop();
        a = dec(b);
        
        bool g = 1;
        for (int i = 0; i < m; ++i) g &= a[2*i] == a[2*i+1];
        if (g) {
            vector<pii> ans;
            while (p[b] != -1) {
                ans.push_back(mov[b]);
                b = p[b];
            }
            reverse(ans.begin(), ans.end());
            cout << ans.size() << '\n';
            for (pii q : ans) cout << q.first << ' ' << q.second << '\n';
            return;
        }
        
        for (int i = 0; i < m; ++i) if (a[2*i] != 0) {
            for (int j = 0; j < m; ++j) if (i != j && a[2*j+1] == 0) {
                int x = a[2*i+1] != 0;
                int y = a[2*j] != 0;
                swap(a[2*i+x], a[2*j+y]);
                int c = enc(a);
                if (!vis[c]) {
                    vis[c] = 1;
                    p[c] = b;
                    mov[c] = {i+1, j+1};
                    bfs.push(c);
                }
                swap(a[2*i+x], a[2*j+y]);
            }
        }
    }
    
    cout << "-1\n";
}

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    
    solve();
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 25
• Subtask 4: 0 / 15
• Subtask 5: 0 / 25
• Subtask 6: 0 / 15