Submission #729078

#	Time	Username	Problem	Language	Result	Execution time	Memory
729078		MohamedFaresNebili	Parking (CEOI22_parking)	C++14	10 / 100	2072 ms	8892 KiB

Main

#include <bits/stdc++.h>

        using namespace std;

        int N, M;
        int B[200005], T[200005];

        int32_t main()
        {
            ios_base::sync_with_stdio(false);
            cin.tie(0); cout.tie(0);
            cin >> N >> M;
            for(int l = 0; l < M; l++)
                cin >> B[l] >> T[l];
            vector<pair<int, int>> res;

            do {
                bool done = true;
                vector<int> emp;
                vector<vector<int>> tp(N + 1), bt(N + 1);
                vector<array<int, 2>> c;
                for(int l = 0; l < M; l++) {
                    done &= ((B[l] == 0) || ((T[l] > 0) && (B[l] == T[l])));
                    if(B[l] == 0) emp.push_back(l);
                    if(B[l] == T[l]) continue;
                    if(T[l] > 0) tp[T[l]].push_back(l);
                    if(T[l] == 0 && B[l] > 0)
                        bt[B[l]].push_back(l);
                    if(tp[T[l]].size() == 2)
                        c.push_back({tp[T[l]][0], tp[T[l]][1]});
                }
                if(done) break;
                bool op = false;
                while(true) {
                    bool ff = false, ss = false;
                    for(int l = 1; l <= N; l++) {
                        if(bt[l].size() < 2) continue;
                        res.push_back({bt[l][0], bt[l][1]});
                        swap(B[bt[l][0]], T[bt[l][1]]);
                        ff = true;
                        break;
                    }
                    op |= ff;
                    if(ff) break;

                    for(int l = 1; l <= N; l++) {
                        if(bt[l].size() != 1 || tp[l].size() != 1)
                            continue;
                        if(bt[l] == tp[l]) continue;
                        res.push_back({tp[l][0], bt[l][0]});
                        swap(T[tp[l][0]], T[bt[l][0]]);
                        ff = true; break;
                    }
                    op |= ff;
                    if(ff) break;

                    if(emp.size() && c.size()) {
                        res.push_back({c.back()[0], emp.back()});
                        res.push_back({c.back()[1], emp.back()});
                        swap(B[emp.back()], T[c.back()[0]]);
                        swap(T[emp.back()], T[c.back()[1]]);
                        ss = true;
                    }
                    op |= ss;
                    if(ss) break;

                    if(emp.size()) {
                        for(int l = 1; l <= N; l++) {
                            if(tp[l].size()) {
                                int i = tp[l][0];
                                if(tp[B[i]].size() > 0) {
                                    res.push_back({tp[l][0], emp.back()});
                                    swap(B[emp.back()], T[tp[l][0]]);
                                    ss = true; break;
                                }
                                if(tp[l].size() == 1)
                                    continue;
                                i = tp[l][1];
                                if(tp[B[i]].size() > 0) {
                                    res.push_back({tp[l][1], emp.back()});
                                    swap(B[emp.back()], T[tp[l][1]]);
                                    ss = true; break;
                                }
                            }
                        }
                    }
                    op |= ss;
                    if(op) break;

                    if(emp.size()) {
                        for(int l = 1; l <= N; l++) {
                            if(tp[l].size()) {
                                res.push_back({tp[l][0], emp.back()});
                                swap(B[emp.back()], T[tp[l][0]]);
                                ss = true; break;
                            }
                        }
                    }
                    op |= ss; break;
                }
                if(!op) {
                    cout << -1; return 0;
                }
            } while(true);
            cout << res.size() << "\n";
            for(auto u : res)
                cout << ++u.first << " " << ++u.second << "\n";
        }

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