Submission #862206

#	Time	Username	Problem	Language	Result	Execution time	Memory
862206		vgtcross	Parking (CEOI22_parking)	C++17	20 / 100	220 ms	19176 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;
    
    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