Submission #677451

# Submission time Handle Problem Language Result Execution time Memory
677451 2023-01-03T11:34:27 Z stanislavpolyn Parking (CEOI22_parking) C++17
0 / 100
91 ms 30528 KB
#include <bits/stdc++.h>

#define fr(i, a, b) for (int i = (a); i <= (b); ++i)
#define rf(i, a, b) for (int i = (a); i >= (b); --i)
#define fe(x, y) for (auto& x : y)

#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define mt make_tuple

#define all(x) (x).begin(), (x).end()
#define pw(x) (1LL << (x))
#define sz(x) (int)(x).size()

using namespace std;

mt19937_64 rng(228);

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define fbo find_by_order
#define ook order_of_key

template <typename T>
bool umn(T& a, T b) {
    return a > b ? (a = b, 1) : 0;
}
template <typename T>
bool umx(T& a, T b) {
    return a < b ? (a = b, 1) : 0;
}

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template <typename T>
using ve = vector<T>;

const int N = 2e5 + 5;

int n, m;
int a[N][2];
ve<pii> opers;
ve<pii> pos[N];
set<int> emp;

void doOper(int i, int j) {
//    cout << "MAKE OPER " << i << " " << j << "\n" << flush;

    assert(i != j);
    assert(a[i][0]);

    int x = a[i][1] ? a[i][1] : a[i][0];

//    cout << "x: " << x << "\n";
    int from = a[i][1] ? 1 : 0;
    assert(!a[j][1]);
    assert(a[j][0] == 0 || a[j][0] == x);
//    cout << i << " " << from << "\n";

    int idx = -1;
    fr (cur, 0, 1) {
        if (pos[x][cur].fi == i && pos[x][cur].se == from) {
            idx = cur;
            break;
        }
    }
    assert(idx != -1);

    if (from == 0) {
        emp.insert(i);
    }

    if (a[j][0] == 0) {
        a[i][from] = 0;
        a[j][0] = x;
        pos[x][idx] = {j, 0};
        emp.erase(j);
    } else {
        assert(a[j][0]);
        a[i][from] = 0;
        a[j][1] = x;
        pos[x][idx] = {j, 1};
    }
    opers.pb({i, j});
}

int main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else
    ios::sync_with_stdio(0);
    cin.tie(0);
#endif

    cin >> n >> m;

    fr (i, 1, m) {
        cin >> a[i][0] >> a[i][1];

        if (a[i][0]) {
            pos[a[i][0]].pb({i, 0});
        }
        if (a[i][1]) {
            pos[a[i][1]].pb({i, 1});
        }
    }

    fr (i, 1, m) {
        if (!a[i][0]) {
            emp.insert(i);
        }
    }

    while (1) {
        bool found = 0;
        int cnt = 0;
        fr (i, 1, n) {
            if (pos[i][0].fi == pos[i][1].fi) {
                cnt++;
                continue;
            }

            int i1 = pos[i][0].fi;
            int j1 = pos[i][0].se;
            int i2 = pos[i][1].fi;
            int j2 = pos[i][1].se;

//            if (i == 2) {
//                cout << "YEP\n";
//                cout << i1 << " " << j1 << " " << i2 << " " << j2 << "\n";
//            }

            if (j1 == 1 || !a[i1][1]) {
                if (j2 == 0 && !a[i2][1]) {

                    doOper(i1, i2);
                    found = 1;
                    continue;
                }
            }
            if (j2 == 1 || !a[i2][1]) {
                if (j1 == 0 && !a[i1][1]) {
                    doOper(i2, i1);
                    found = 1;
                }
            }

        }

        if (cnt == n) {
            fr (i, 1, m) {
                if (a[i][0]) {
                    assert(a[i][0] == a[i][1]);
                }
            }

            assert(0);

            cout << sz(opers) << "\n";
            fe (x, opers) {
                cout << x.fi << " " << x.se << "\n";
            }
            return 0;
        }

        if (found) {
            continue;
        }

        fr (i, 1, n) {
            if (pos[i][0].fi == pos[i][1].fi) {
                continue;
            }

            int i1 = pos[i][0].fi;
            int j1 = pos[i][0].se;
            int i2 = pos[i][1].fi;
            int j2 = pos[i][1].se;

            if (j1 == 1 && j2 == 1) {
                if (sz(emp)) {
                    int to = *emp.begin();
                    doOper(i1, to);
                    doOper(i2, to);
                    found = 1;
                }
            }
        }

        if (found) {
            continue;
        }

//        cout << "YEP HERE\n";

        fr (i, 1, n) {
            if (pos[i][0].fi == pos[i][1].fi) {
               continue;
            }

            int i1 = pos[i][0].fi;
            int j1 = pos[i][0].se;
            int i2 = pos[i][1].fi;
            int j2 = pos[i][1].se;

            if (j1 != j2) {
                if (j1 == 0) {
                    if (!sz(emp)) {
                        cout << "-1\n";
                        return 0;
                    }
                    int to = *emp.begin();
                    doOper(i1, to);
                    found = 1;
                    break;
                }
                if (j2 == 0) {
                    if (!sz(emp)) {
                        cout << "-1\n";
                        return 0;
                    }
                    int to = *emp.begin();
                    doOper(i2, to);
                    found = 1;
                    break;
                }
            }
        }

        if (!found) {
            cout << "-1\n";
            return 0;
        }
    }

    return 0;
}
# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 9940 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 91 ms 30528 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 10068 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 9940 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -