oj.uz

Submission #729035

# Submission time Handle Problem Language Result Execution time Memory
729035 2023-04-23T12:12:33 Z MohamedFaresNebili Parking (CEOI22_parking) C++14
0 / 100
 176 ms 8840 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;
            int calc = 0;

            do {
                bool done = true;
                calc++;
                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()) {
                                res.push_back({tp[l].back(), emp.back()});
                                swap(B[emp.back()], T[tp[l].back()]);
                                ss = true; break;
                            }
                        }
                    }
                    op != ss; break;
                }
                if(!op) {
                    cout << -1; return 0;
                }
            } while(calc < 10);
            cout << res.size() << "\n";
            for(auto u : res)
                cout << ++u.first << " " << ++u.second << "\n";
        }

Compilation message

Main.cpp: In function 'int32_t main()':
Main.cpp:78:24: warning: statement has no effect [-Wunused-value]
   78 |                     op != ss; break;
      |                     ~~~^~~~~

Subtask #1
0.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 Incorrect 0 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0.0 / 10.0

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

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 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 1 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 Incorrect 1 ms 340 KB Output isn't correct
2 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 Incorrect 0 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -