Submission #1223601

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223601		overwatch9	Parking (CEOI22_parking)	C++20	2 / 100	2094 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) {
        bool done = false;
        // first move a top car to the top of another pile
        set <pair <int, int>> bottoms;
        for (int i = 1; i <= m; i++) {
            if (a[i] == b[i])
                continue;
            if (a[i] == 0)
                continue;
            if (b[i] == 0)
                bottoms.insert({a[i], i});
        }
        for (int i = 1; i <= m; i++) {
            if (a[i] == b[i])
                continue;
            if (b[i] == 0)
                continue;
            auto it = bottoms.lower_bound({b[i], 0});
            if (it != bottoms.end() && it->first == b[i]) {
                ans++;
                steps.push_back({i, it->second});
                done = true;
                b[i] = 0;
                b[it->second] = a[it->second];
                break;
            }
        }
        if (done)
            continue;

        // now try to move a[x] to b[y]
        set <pair <int, int>> tops;
        for (int i = 1; i <= m; i++) {
            if (a[i] == b[i])
                continue;
            if (b[i] == 0 && a[i] != 0) {
                auto it = tops.lower_bound({a[i], 0});
                if (it != tops.end() && it->first == a[i]) {
                    ans++;
                    steps.push_back({it->second, i});
                    a[i] = 0;
                    b[it->second] = a[it->second];
                    done = true;
                    break;
                } else {
                    tops.insert({a[i], i});
                }
            }
        }
        if (done)
            continue;

        // now try to make a base for a number that doesn't have one
        set <int> seen;
        int empty = -1;
        for (int i = 1; i <= m; i++) {
            if (a[i] == 0) {
                empty = i;
                continue;
            }
            seen.insert(a[i]);
        }

        for (int i = 1; i <= m; i++) {
            if (b[i] == 0)
                continue;
            if (b[i] == a[i])
                continue;

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

        // try creating a new base
        seen.clear();
        empty = -1;
        for (int i = 1; i <= m; i++) {
            if (a[i] == 0)
                empty = i;
            else if (a[i] != b[i] && b[i] != 0)
                seen.insert(a[i]);
        }
        if (empty == -1) {
            cout << -1 << '\n';
            return 0;
        }
        for (int i = 1; i <= m; i++) {
            if (b[i] == 0)
                continue;
            if (a[i] == b[i])
                continue;
            auto it = seen.lower_bound(b[i]);
            if (it != seen.end() && *it == b[i]) {
                done = true;
                ans++;
                steps.push_back({i, empty});
                a[empty] = b[i];
                b[i] = 0;
                break;
            }
        }
        if (done)
            continue;

        if (!done)
            break;
    }
    for (int i = 1; i <= m; i++) {
        if (a[i] != b[i]) {
            cout << -1 << '\n';
            return 0;
        }
    }

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

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