Submission #1227778

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227778		spetr	Parking (CEOI22_parking)	C++20	100 / 100	127 ms	29416 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define ll long long
const ll mmod = 998244353;
#define vl vector<ll>
#define vvl vector<vl>
#define pl pair<ll, ll>
#define vb vector<bool>

ll n, m;
vvl stk;
vl emp;
vvl at;
vector<pl> res;

void fail() {
    cout << -1 << '\n';
    exit(0);
}

void atob(ll a, ll b) {
    ll v = stk[a].back();
    stk[a].pop_back();
    stk[b].push_back(v);
    for (ll &x : at[v]) if (x == a) { x = b; break; }
    res.emplace_back(a, b);
}

ll other(ll x, ll p) {
    // at[x] has size 2
    return at[x][0] ^ at[x][1] ^ p;
}

ll shift(ll p) {
    ll v = stk[p][0];
    ll o = other(v, p);
    while (stk[o].size() == 2 && stk[o][1] == v) {
        atob(o, p);
        p = o;
        v = stk[p][0];
        o = other(v, p);
    }
    return p;
}

ll eqtop(ll p) {
    ll v = stk[p][1];
    ll o = other(v, p);
    while (stk[o][0] == v) {
        p = o;
        v = stk[p][1];
        o = other(v, p);
    }
    return p;
}

void take_care(ll p) {
    if (emp.empty()) fail();
    if (stk[p].empty()) {
        emp.push_back(p);
        return;
    }
    // size == 1
    ll v = stk[p][0];
    ll e = emp.back();
    ll o = other(v, p);
    if (stk[o].size() == 1 || stk[o][1] == v) {
        atob(o, p);
        take_care(o);
        return;
    }
    ll g = eqtop(o);
    atob(g, e);
    shift(g);
    atob(o, p);
    emp.back() = o;
    take_care(e);
}

void no_more_care(ll p) {
    if (stk[p].empty()) {
        emp.push_back(p);
        return;
    }
    // size == 1
    ll v = stk[p][0];
    ll o = other(v, p);
    if (stk[o].back() == v) {
        atob(o, p);
        no_more_care(o);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    stk.assign(m, vl());
    at.assign(n + 1, vl());

    for (ll i = 0; i < m; i++) {
        ll b, t;
        cin >> b >> t;
        for (ll j : {b, t}) if (j) {
            stk[i].push_back(j);
            at[j].push_back(i);
        }
        if (b == 0) emp.push_back(i);
    }

    for (ll i = 0; i < m; i++) if (stk[i].size() == 1) no_more_care(i);
    for (ll i = 0; i < m; i++) if (stk[i].size() == 1) take_care(i);

    for (ll i = 1; i <= n; i++) {
        ll a = at[i][0], b = at[i][1];
        if (a == b) continue;
        if (stk[a].size() + stk[b].size() == 4 && stk[a].back() == i && stk[b].back() == i) {
            if (emp.empty()) fail();
            ll e = emp.back(); emp.pop_back();
            atob(a, e);
            atob(b, e);
            a = shift(a); b = shift(b);
            if (stk[a][0] == stk[b][0]) {
                atob(a, b);
                emp.push_back(a);
            } else {
                take_care(a);
            }
        }
    }

    for (ll i = 1; i <= n; i++) {
        ll a = at[i][0], b = at[i][1];
        if (a == b) continue;
        if (emp.empty()) fail();
        if (stk[a][0] != i) swap(a, b);
        ll e = emp.back();
        atob(a, e);
        ll g = shift(a);
        atob(e, g);
    }

    for (ll i = 1; i <= n; i++) assert(at[i][0] == at[i][1]);

    cout << res.size() << '\n';
    for (auto &pr : res) {
        cout << pr.first + 1 << ' ' << pr.second + 1 << '\n';
    }
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 25 / 25
• Subtask 4: 15 / 15
• Subtask 5: 25 / 25
• Subtask 6: 15 / 15