oj.uz

Submission #729078

# Submission time Handle Problem Language Result Execution time Memory
729078 2023-04-23T13:11:45 Z MohamedFaresNebili Parking (CEOI22_parking) C++14
10 / 100
 2000 ms 8892 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 324 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 332 KB Output is correct

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2072 ms 8892 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 408 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 34 ms 420 KB Output is correct
4 Correct 13 ms 388 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 46 ms 412 KB Output is correct
7 Correct 6 ms 340 KB Output is correct
8 Incorrect 6 ms 340 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #6
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 324 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Execution timed out 2072 ms 8892 KB Time limit exceeded
12 Halted 0 ms 0 KB -