oj.uz

Submission #762248

# Submission time Handle Problem Language Result Execution time Memory
762248 2023-06-21T07:01:24 Z resting Parking (CEOI22_parking) C++17
50 / 100
 525 ms 33332 KB 
#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);
        if (x[0] + x[1] == -2) empty.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); }
    }

    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
0.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 20184 KB Output is correct
2 Correct 258 ms 20808 KB Output is correct
3 Correct 153 ms 18240 KB Output is correct
4 Correct 144 ms 17872 KB Output is correct
5 Correct 246 ms 20980 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 360 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 3 ms 468 KB Output is correct
8 Correct 1 ms 308 KB Output is correct
9 Correct 4 ms 468 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 360 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 3 ms 468 KB Output is correct
8 Correct 1 ms 308 KB Output is correct
9 Correct 4 ms 468 KB Output is correct
10 Correct 525 ms 32924 KB Output is correct
11 Correct 114 ms 25524 KB Output is correct
12 Correct 149 ms 25516 KB Output is correct
13 Correct 456 ms 31396 KB Output is correct
14 Correct 157 ms 26188 KB Output is correct
15 Correct 148 ms 25276 KB Output is correct
16 Correct 503 ms 33332 KB Output is correct
17 Correct 141 ms 25036 KB Output is correct
18 Correct 481 ms 32608 KB Output is correct

Subtask #5
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0.0 / 15.0

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