oj.uz

답안 #862206

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
862206 2023-10-17T17:17:00 Z vgtcross Parking (CEOI22_parking) C++17
20 / 100
 220 ms 19176 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;
    
    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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 344 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 120 ms 16456 KB Output is correct
2 Correct 220 ms 19176 KB Output is correct
3 Correct 78 ms 12992 KB Output is correct
4 Correct 70 ms 12104 KB Output is correct
5 Correct 162 ms 19008 KB Output is correct

Subtask #3
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 344 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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 120 ms 16456 KB Output is correct
12 Correct 220 ms 19176 KB Output is correct
13 Correct 78 ms 12992 KB Output is correct
14 Correct 70 ms 12104 KB Output is correct
15 Correct 162 ms 19008 KB Output is correct
16 Incorrect 1 ms 344 KB Output isn't correct
17 Halted 0 ms 0 KB -