Submission #862203

#	Time	Username	Problem	Language	Result	Execution time	Memory
862203		vgtcross	Parking (CEOI22_parking)	C++17	20 / 100	212 ms	18240 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;
    
    if (m <= 4) {
        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";
    } else {
        vector<array<int, 2>> g(m+1);
        vector<vector<int>> pos(n+1);
        vector<int> abv(n+1, 0);
        set<int> rem;
        vector<int> f;
        for (int i = 0; i < m; ++i) {
            int a, b;
            cin >> a >> b;
            g[i][0] = a;
            g[i][1] = b;
            if (a) pos[a].push_back(i);
            if (b) pos[b].push_back(i);
            if (a != 0 && a != b) {
                rem.insert(a);
                if (b != 0) rem.insert(b);
            }
            if (b != 0) ++abv[a];
            if (a == 0 && b == 0) f.push_back(i);
        }
        
        vector<pii> ans;
        set<int> nx, nx2;
        for (int i = 1; i <= n; ++i) if (rem.count(i) && abv[i] == 0) {
            if (g[pos[i][0]][0] == i || g[pos[i][1]][0] == i) nx.insert(i);
            else nx2.insert(i);
        }
        while (rem.size()) {
            if (nx.size()) {
                int a = *nx.begin();
                int i = pos[a][0];
                int j = pos[a][1];
                if (g[i][0] == a && g[j][0] == a) {
                    ans.push_back({j, i});
                    swap(g[i][1], g[j][0]);
                    pos[a][1] = i;
                    f.push_back(j);
                } else if (g[i][0] == a && g[j][1] == a) {
                    ans.push_back({j, i});
                    swap(g[i][1], g[j][1]);
                    pos[a][1] = i;
                    if (--abv[g[j][0]] == 0) {
                        if (g[pos[g[j][0]][0]][0] == g[j][0] || g[pos[g[j][0]][1]][0] == g[j][0]) nx.insert(g[j][0]);
                        else nx2.insert(g[j][0]);
                    }
                } else {
                    ans.push_back({i, j});
                    swap(g[j][1], g[i][1]);
                    pos[a][0] = i;
                    if (--abv[g[i][0]] == 0) {
                        if (g[pos[g[i][0]][0]][0] == g[i][0] || g[pos[g[i][0]][1]][0] == g[i][0]) nx.insert(g[i][0]);
                        else nx2.insert(g[i][0]);
                    }
                }
                nx.erase(a);
                rem.erase(a);
            } else if (nx2.size()) {
                int a = *nx2.begin();
                int i = pos[a][0];
                int j = pos[a][1];
                if (f.empty()) {
                    cout << "-1\n";
                    return;
                }
                int k = f.back();
                f.pop_back();
                ans.push_back({i, k});
                ans.push_back({j, k});
                swap(g[k][0], g[i][1]);
                swap(g[k][1], g[j][1]);
                pos[a][0] = k;
                pos[a][1] = k;
                if (--abv[g[i][0]] == 0) {
                    if (g[pos[g[i][0]][0]][0] == g[i][0] || g[pos[g[i][0]][1]][0] == g[i][0]) nx.insert(g[i][0]);
                    else nx2.insert(g[i][0]);
                }
                if (--abv[g[j][0]] == 0) {
                    if (g[pos[g[j][0]][0]][0] == g[j][0] || g[pos[g[j][0]][1]][0] == g[j][0]) nx.insert(g[j][0]);
                    else nx2.insert(g[j][0]);
                }
                nx2.erase(a);
                rem.erase(a);
            } else {
                int a = *rem.begin();
                int i = pos[a][0];
                int j = pos[a][1];
                if (f.empty()) {
                    cout << "-1\n";
                    return;
                }
                int k = f.back();
                f.pop_back();
                if (g[i][1] == a) {
                    ans.push_back({i, k});
                    swap(g[k][0], g[i][1]);
                    pos[a][0] = k;
                    if (--abv[g[i][0]] == 0) {
                        if (g[pos[g[i][0]][0]][0] == g[i][0] || g[pos[g[i][0]][1]][0] == g[i][0]) nx.insert(g[i][0]);
                        else nx2.insert(g[i][0]);
                    }
                } else {
                    ans.push_back({j, k});
                    swap(g[k][0], g[j][1]);
                    pos[a][1] = k;
                    if (--abv[g[j][0]] == 0) {
                        if (g[pos[g[j][0]][0]][0] == g[j][0] || g[pos[g[j][0]][1]][0] == g[j][0]) nx.insert(g[j][0]);
                        else nx2.insert(g[j][0]);
                    }
                }
            }
        }
        
        cout << ans.size() << '\n';
        for (pii p : ans) cout << p.first+1 << ' ' << p.second+1 << '\n';
    }
}

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

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