제출 #1097327

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1097327		gyg	Parking (CEOI22_parking)	C++17	10 / 100	2075 ms	33416 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define arr array 
#define vct vector 
#define pii pair<int, int>
#define mpii make_pair
#define fir first 
#define sec second 
#define hset unordered_set
const int N = 2e5 + 5, M = 2e5 + 5;

int n, m;
arr<arr<int, 2>, M> vl;
arr<pii, N> ps;

int fr(int i) { 
    assert(i != 0);
    return ((i <= n) ? i + n : i - n); 
} 
void prcmp() {
    hset<int> vls;
    for (int i = 1; i <= m; i++) {
        for (int j = 0; j <= 1; j++) {
            if (vl[i][j] == 0) continue;
            if (!vls.count(vl[i][j])) vls.insert(vl[i][j]);
            else vl[i][j] += n;
            ps[vl[i][j]] = {i, j};
        }
    }
}

vct<pii> ans;
void mv(int i, int j) {
    ans.push_back({i, j});
    int k = (vl[i][1] != 0) ? vl[i][1] : vl[i][0];
    vl[ps[k].fir][ps[k].sec] = 0;
    ps[k] = (vl[j][0] == 0) ? mpii(j, 0) : mpii(j, 1);
    vl[ps[k].fir][ps[k].sec] = k;
}
bool fn() {
    for (int i = 1; i <= n; i++)
        if (ps[i].fir != ps[fr(i)].fir) return false;
    return true;
}

void cmp() {
    // for (int i = 1; i <= m; i++) {
    //     cout << vl[i][0] << " " << vl[i][1] << endl;
    // }

    while (true) {
        if (fn()) break;

        bool flg = false;
        for (int i = 1; i <= m; i++) {
            int j = vl[i][0];
            if (j != 0 && vl[i][1] == 0 && (ps[fr(j)].sec == 1 || vl[ps[fr(j)].fir][1] == 0)) {
                mv(ps[fr(j)].fir, i);
                flg = true; break;
            }
        }
        if (flg) continue;

        int emp = 0;
        for (int i = 1; i <= m; i++)
            if (vl[i][0] == 0) emp = i;
        if (emp == 0) { cout << -1 << endl; exit(0); }

        for (int i = 1; i <= n; i++) {
            if (ps[i].sec == 1 && ps[fr(i)].sec == 1) {
                mv(ps[i].fir, emp);
                flg = true; break;
            }
        }
        if (flg) continue;
        for (int i = 1; i <= n; i++) {
            if (ps[i].sec == 1) {
                mv(ps[i].fir, emp);
                break;
            }
        }
    }

    // for (int i = 1; i <= m; i++) {
    //     cout << vl[i][0] << " " << vl[i][1] << endl;
    // }
}

int main() {
    // freopen("prk.in", "r", stdin);
    cin >> n >> m;
    for (int i = 1; i <= m; i++) 
        for (int j = 0; j <= 1; j++) 
            cin >> vl[i][j];

    prcmp();
    cmp();
    
    cout << ans.size() << endl;
    for (pii x : ans) cout << x.fir << " " << x.sec << endl;
}

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