제출 #762252

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
762252		resting	Parking (CEOI22_parking)	C++17	100 / 100	541 ms	33292 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int mx = 1e5 + 5;
void solve() {
    int n, m; cin >> n >> m;
    vector<vector<int>> v(m, vector<int>(2, 0));
    vector<vector<int>> pos(n);
    vector<int> empty;
    vector<pair<int, int>> res;
    for (int i = 0; i < m; i++) {
        auto& x = v[i];
        cin >> x[0] >> x[1]; x[0]--; x[1]--;
        if (x[0] + 1) pos[x[0]].push_back(i);
        if (x[1] + 1) pos[x[1]].push_back(i);
    }

    vector<int> vis(n, 0);

    auto mov = [&](int x, int y) -> void {
        res.push_back({ x, y });
        if (v[x][1] + 1) {
            if (v[y][0] + 1) swap(v[x][1], v[y][1]);
            else swap(v[x][1], v[y][0]);
        } else {
            if (v[y][0] + 1) swap(v[x][0], v[y][1]);
            else swap(v[x][0], v[y][0]);
        }
    };



    //case 1: trivial case
    auto good = [&](int x) -> bool {
        for (int i = 0; i < 2; i++) {
            if (v[pos[x][0]][1] == -1 && (v[pos[x][1]][1] == x || v[pos[x][1]][1] == -1)) {
                return true;
            }
            swap(pos[x][0], pos[x][1]);
        }
        return false;
    };


    vector<int> q;
    for (int i = 0; i < n; i++) {
        if (pos[i][0] == pos[i][1]) {
            vis[i] = 1;
            continue;
        }
        if (good(i)) {
            q.push_back(i); vis[i] = 1;
        }
    }

    while (!q.empty()) {
        auto x = q.back();
        q.pop_back();
        // cout << "good: " << x << endl;
        mov(pos[x][1], pos[x][0]);
        auto t = v[pos[x][1]][0];
        if (t != -1 && good(t)) { vis[t] = 1; q.push_back(t); }
    }
    for (int i = 0; i < m; i++) {
        auto& x = v[i];
        if (x[0] + x[1] == -2) empty.push_back(i);
    }
    vector<int> todo;

    bool bad = 0;

    auto clear = [&](int t) {
        if (t == -1) return;
        for (int j = 0; j < 2; j++) {
            // cout << t << "," << pos[t][0] << "," << v[pos[t][0]][1] << endl;
            if (v[pos[t][0]][1] == -1) {
                while (true) {
                    //cout << "t: " << t << endl;
                    if (t != -1) vis[t] = 1;
                    if (t == -1) {
                        //process
                        reverse(todo.begin(), todo.end());
                        empty.push_back(pos[todo.back()][0]);
                        for (auto& x : todo) {
                            mov(pos[x][0], pos[x][1]);
                        }
                        todo.clear();
                        return;
                    } else if (v[pos[t][1]][1] == t) {
                        if (v[pos[t][0]][1] == t) {
                            if (!empty.size()) { cout << -1 << endl;bad = 1;  return; }
                            mov(pos[t][0], empty.back());
                            mov(pos[t][1], empty.back());
                            empty.pop_back();

                            //process
                            reverse(todo.begin(), todo.end());
                            empty.push_back(pos[todo.back()][0]);
                            for (auto& x : todo) {
                                mov(pos[x][0], pos[x][1]);
                            }
                            todo.clear();
                        } else {
                            mov(pos[t][1], pos[t][0]);
                        }
                        t = v[pos[t][1]][0];
                        if (v[pos[t][0]][1] != -1) swap(pos[t][0], pos[t][1]);
                    } else {
                        todo.push_back(t); vis[t] = 1;
                        int p = t;
                        t = v[pos[t][1]][1];
                        if (t != -1 && v[pos[t][0]][0] != p) swap(pos[t][0], pos[t][1]);
                    }
                }
            }
            swap(pos[t][0], pos[t][1]);
        }
    };

    //cout << "case2" << endl;
    //case 2 - strip
    for (int i = 0; i < n; i++) {
        if (vis[i]) continue;
        int t = i;
        clear(t);
        if (bad) return;
    }

    //cout << "case3" << endl;
    //case 3 - circle
    for (int i = 0; i < n; i++) {
        if (vis[i]) continue;
        int t = i;
        if (v[pos[t][0]][1] == t && v[pos[t][1]][1] == t) {
            vis[t] = 1;
            if (!empty.size()) { cout << -1 << endl;return; }
            mov(pos[t][0], empty.back());
            mov(pos[t][1], empty.back());
            empty.pop_back();
            t = v[pos[t][0]][0];
            clear(t); if (bad) return;
        }
    }
    // cout << "case4" << endl;
     //case 4 - finish them
    for (int i = 0; i < n; i++) {
        if (vis[i]) continue;
        int t = i; vis[t] = 1;
        if (v[pos[t][0]][1] != t) swap(pos[t][0], pos[t][1]);
        if (!empty.size()) { cout << -1 << endl;return; }
        int bk = empty.back();
        mov(pos[t][0], bk); pos[t][0] = bk;
        t = v[pos[t][0]][0];

        clear(t);
        if (bad) return;
    }



    cout << res.size() << endl;
    for (auto& x : res) cout << x.first + 1 << " " << x.second + 1 << endl;

    //cout << "result: " << endl;
    //for (auto& x : v) cout << x[0] + 1 << " " << x[1] + 1 << endl;


}

int32_t main() {
    int t = 1;
    //cin >> t;
    while (t--)
        solve();
}

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