oj.uz

Submission #862167

# Submission time Handle Problem Language Result Execution time Memory
862167 2023-10-17T15:15:54 Z vgtcross Parking (CEOI22_parking) C++17
10 / 100
 9 ms 16476 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;
    
    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";
}

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 8280 KB Output is correct
2 Correct 2 ms 8124 KB Output is correct
3 Correct 2 ms 8112 KB Output is correct
4 Correct 2 ms 8288 KB Output is correct
5 Correct 2 ms 8288 KB Output is correct
6 Correct 3 ms 8280 KB Output is correct
7 Correct 3 ms 8280 KB Output is correct
8 Correct 2 ms 8292 KB Output is correct
9 Correct 2 ms 8280 KB Output is correct
10 Correct 2 ms 8284 KB Output is correct

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 600 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 16476 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 16476 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 348 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8280 KB Output is correct
2 Correct 2 ms 8124 KB Output is correct
3 Correct 2 ms 8112 KB Output is correct
4 Correct 2 ms 8288 KB Output is correct
5 Correct 2 ms 8288 KB Output is correct
6 Correct 3 ms 8280 KB Output is correct
7 Correct 3 ms 8280 KB Output is correct
8 Correct 2 ms 8292 KB Output is correct
9 Correct 2 ms 8280 KB Output is correct
10 Correct 2 ms 8284 KB Output is correct
11 Runtime error 1 ms 600 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -