oj.uz

Submission #862203

# Submission time Handle Problem Language Result Execution time Memory
862203 2023-10-17T17:13:39 Z vgtcross Parking (CEOI22_parking) C++17
20 / 100
 212 ms 18240 KB 
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using pii = pair<ll, ll>;

int enc(array<int, 8> &a) {
    int b = 0;
    for (int i : a) b = 5*b + i;
    return b;
}

array<int, 8> dec(int b) {
    array<int, 8> a;
    for (int i = 7; i >= 0; --i) {
        a[i] = b % 5;
        b /= 5;
    }
    return a;
}

void solve() {
    int n, m;
    cin >> n >> m;
    
    if (m <= 4) {
        array<int, 8> a;
        for (int i = 0; i < 2*m; ++i) cin >> a[i];

        vector<bool> vis(4e5, 0);
        vector<int> p(4e5);
        vector<pii> mov(4e5);

        int b = enc(a);
        vis[b] = 1;
        p[b] = -1;
        queue<int> bfs;
        bfs.push(b);
        while (bfs.size()) {
            b = bfs.front();
            bfs.pop();
            a = dec(b);

            bool g = 1;
            for (int i = 0; i < m; ++i) g &= a[2*i] == a[2*i+1];
            if (g) {
                vector<pii> ans;
                while (p[b] != -1) {
                    ans.push_back(mov[b]);
                    b = p[b];
                }
                reverse(ans.begin(), ans.end());
                cout << ans.size() << '\n';
                for (pii q : ans) cout << q.first << ' ' << q.second << '\n';
                return;
            }

            for (int i = 0; i < m; ++i) if (a[2*i] != 0) {
                for (int j = 0; j < m; ++j) if (i != j && a[2*j+1] == 0) {
                    int x = a[2*i+1] != 0;
                    int y = a[2*j] != 0;
                    swap(a[2*i+x], a[2*j+y]);
                    int c = enc(a);
                    if (!vis[c]) {
                        vis[c] = 1;
                        p[c] = b;
                        mov[c] = {i+1, j+1};
                        bfs.push(c);
                    }
                    swap(a[2*i+x], a[2*j+y]);
                }
            }
        }

        cout << "-1\n";
    } else {
        vector<array<int, 2>> g(m+1);
        vector<vector<int>> pos(n+1);
        vector<int> abv(n+1, 0);
        set<int> rem;
        vector<int> f;
        for (int i = 0; i < m; ++i) {
            int a, b;
            cin >> a >> b;
            g[i][0] = a;
            g[i][1] = b;
            if (a) pos[a].push_back(i);
            if (b) pos[b].push_back(i);
            if (a != 0 && a != b) {
                rem.insert(a);
                if (b != 0) rem.insert(b);
            }
            if (b != 0) ++abv[a];
            if (a == 0 && b == 0) f.push_back(i);
        }
        
        vector<pii> ans;
        set<int> nx, nx2;
        for (int i = 1; i <= n; ++i) if (rem.count(i) && abv[i] == 0) {
            if (g[pos[i][0]][0] == i || g[pos[i][1]][0] == i) nx.insert(i);
            else nx2.insert(i);
        }
        while (rem.size()) {
            if (nx.size()) {
                int a = *nx.begin();
                int i = pos[a][0];
                int j = pos[a][1];
                if (g[i][0] == a && g[j][0] == a) {
                    ans.push_back({j, i});
                    swap(g[i][1], g[j][0]);
                    pos[a][1] = i;
                    f.push_back(j);
                } else if (g[i][0] == a && g[j][1] == a) {
                    ans.push_back({j, i});
                    swap(g[i][1], g[j][1]);
                    pos[a][1] = i;
                    if (--abv[g[j][0]] == 0) {
                        if (g[pos[g[j][0]][0]][0] == g[j][0] || g[pos[g[j][0]][1]][0] == g[j][0]) nx.insert(g[j][0]);
                        else nx2.insert(g[j][0]);
                    }
                } else {
                    ans.push_back({i, j});
                    swap(g[j][1], g[i][1]);
                    pos[a][0] = i;
                    if (--abv[g[i][0]] == 0) {
                        if (g[pos[g[i][0]][0]][0] == g[i][0] || g[pos[g[i][0]][1]][0] == g[i][0]) nx.insert(g[i][0]);
                        else nx2.insert(g[i][0]);
                    }
                }
                nx.erase(a);
                rem.erase(a);
            } else if (nx2.size()) {
                int a = *nx2.begin();
                int i = pos[a][0];
                int j = pos[a][1];
                if (f.empty()) {
                    cout << "-1\n";
                    return;
                }
                int k = f.back();
                f.pop_back();
                ans.push_back({i, k});
                ans.push_back({j, k});
                swap(g[k][0], g[i][1]);
                swap(g[k][1], g[j][1]);
                pos[a][0] = k;
                pos[a][1] = k;
                if (--abv[g[i][0]] == 0) {
                    if (g[pos[g[i][0]][0]][0] == g[i][0] || g[pos[g[i][0]][1]][0] == g[i][0]) nx.insert(g[i][0]);
                    else nx2.insert(g[i][0]);
                }
                if (--abv[g[j][0]] == 0) {
                    if (g[pos[g[j][0]][0]][0] == g[j][0] || g[pos[g[j][0]][1]][0] == g[j][0]) nx.insert(g[j][0]);
                    else nx2.insert(g[j][0]);
                }
                nx2.erase(a);
                rem.erase(a);
            } else {
                int a = *rem.begin();
                int i = pos[a][0];
                int j = pos[a][1];
                if (f.empty()) {
                    cout << "-1\n";
                    return;
                }
                int k = f.back();
                f.pop_back();
                if (g[i][1] == a) {
                    ans.push_back({i, k});
                    swap(g[k][0], g[i][1]);
                    pos[a][0] = k;
                    if (--abv[g[i][0]] == 0) {
                        if (g[pos[g[i][0]][0]][0] == g[i][0] || g[pos[g[i][0]][1]][0] == g[i][0]) nx.insert(g[i][0]);
                        else nx2.insert(g[i][0]);
                    }
                } else {
                    ans.push_back({j, k});
                    swap(g[k][0], g[j][1]);
                    pos[a][1] = k;
                    if (--abv[g[j][0]] == 0) {
                        if (g[pos[g[j][0]][0]][0] == g[j][0] || g[pos[g[j][0]][1]][0] == g[j][0]) nx.insert(g[j][0]);
                        else nx2.insert(g[j][0]);
                    }
                }
            }
        }
        
        cout << ans.size() << '\n';
        for (pii p : ans) cout << p.first+1 << ' ' << p.second+1 << '\n';
    }
}

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    
    solve();
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8284 KB Output is correct
2 Correct 3 ms 8280 KB Output is correct
3 Correct 3 ms 8536 KB Output is correct
4 Correct 2 ms 8280 KB Output is correct
5 Correct 3 ms 8280 KB Output is correct
6 Correct 2 ms 8284 KB Output is correct
7 Correct 2 ms 8284 KB Output is correct
8 Correct 3 ms 8536 KB Output is correct
9 Correct 2 ms 8284 KB Output is correct
10 Correct 2 ms 8280 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 15392 KB Output is correct
2 Correct 148 ms 18240 KB Output is correct
3 Correct 78 ms 12352 KB Output is correct
4 Correct 82 ms 11364 KB Output is correct
5 Correct 212 ms 17984 KB Output is correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 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 348 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 1 ms 604 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 600 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Incorrect 1 ms 348 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 2 ms 8284 KB Output is correct
2 Correct 3 ms 8280 KB Output is correct
3 Correct 3 ms 8536 KB Output is correct
4 Correct 2 ms 8280 KB Output is correct
5 Correct 3 ms 8280 KB Output is correct
6 Correct 2 ms 8284 KB Output is correct
7 Correct 2 ms 8284 KB Output is correct
8 Correct 3 ms 8536 KB Output is correct
9 Correct 2 ms 8284 KB Output is correct
10 Correct 2 ms 8280 KB Output is correct
11 Correct 125 ms 15392 KB Output is correct
12 Correct 148 ms 18240 KB Output is correct
13 Correct 78 ms 12352 KB Output is correct
14 Correct 82 ms 11364 KB Output is correct
15 Correct 212 ms 17984 KB Output is correct
16 Incorrect 1 ms 348 KB Output isn't correct
17 Halted 0 ms 0 KB -