Submission #1223484

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223484		overwatch9	Parking (CEOI22_parking)	C++20	0 / 100	2093 ms	6216 KiB

Main

#include <bits/stdc++.h>
using namespace std;
int n, m;
vector <int> a, b;
int main() {
    cin >> n >> m;
    a = b = vector <int> (m+1);
    for (int i = 1; i <= m; i++)
        cin >> a[i] >> b[i];
    int ans = 0;
    vector <pair <int, int>> steps;
    while (true) {
        set <pair <int, int>> to_add;
        for (int i = 1; i <= m; i++) {
            if (b[i] == 0 && a[i] != 0)
                to_add.insert({a[i], i});
        }
        bool done = false;
        for (int i = 1; i <= m; i++) {
            if (b[i] == a[i] || b[i] == 0)
                continue;
            if (a[i] == b[i] && a[i] != 0)
                continue;
            auto it = to_add.lower_bound({b[i], 0});
            if (it != to_add.end() && it->first == b[i]) {
                done = true;
                ans ++;
                steps.push_back({i, it->second});
                b[it->second] = b[i];
                b[i] = 0;
                break;
            }
        }
        if (done)
            continue;

        to_add.clear();
        for (int i = 1; i <= m; i++) {
            if (b[i] != 0)
                continue;
            if (a[i] == b[i] && a[i] != 0)
                continue;
            auto it = to_add.lower_bound({a[i], 0});
            if (it != to_add.end() && it->first == a[i]) {
                ans++;
                steps.push_back({i, it->second});
                b[it->second] = a[i];
                a[i] = 0;
                done = true;
                break;
            } else if (a[i] != 0)
                to_add.insert({a[i], i});
        }
        if (done)
            continue;

        set <int> seen;
        int empty = -1;
        for (int i = 1; i <= m; i++) {
            if (a[i] == 0)
                empty = i;
            else
                seen.insert(a[i]);
        }
        for (int i = 1; i <= m; i++) {
            if (b[i] == 0)
                continue;
            if (a[i] == b[i] && a[i] != 0)
                continue;
            if (seen.find(b[i]) == seen.end()) {
                if (empty == -1) {
                    cout << -1 << '\n';
                    return 0;
                }
                a[empty] = b[i];
                b[i] = 0;
                done = true;
                ans++;
                steps.push_back({i, empty});
                break;
            }
        }
        if (done)
            continue;

        if (!done)
            break;
    }
    cout << ans << '\n';
    for (auto i : steps)
        cout << i.first << ' ' << i.second << '\n';
}

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