oj.uz

Submission #1097343

# Submission time Handle Problem Language Result Execution time Memory
1097343 2024-10-07T01:27:29 Z gyg Parking (CEOI22_parking) C++17
0 / 100
 2000 ms 7268 KB 
#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) {
    assert(i != j), assert(vl[i][0] != 0);
    ans.push_back({i, j});
    int k = (vl[i][1] != 0) ? vl[i][1] : vl[i][0];
    assert(vl[j][0] == 0 || vl[j][0] == fr(k));
    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 <= 2 * 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 <= 2 * n; i++) {
            int j = ps[i].fir;
            int k = fr(i);
            if (vl[j][1] == 0 && (ps[k].sec == 1 || vl[ps[k].fir][1] == 0)) {
                mv(ps[k].fir, j);
                flg = true; break;
            }
        }
        if (flg) continue;

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

        for (int i = 1; i <= 2 * 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 <= 2 * n; i++) {
            if (ps[i].sec == 1 && ps[i].fir != ps[fr(i)].fir) {
                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
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Runtime error 1 ms 604 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2072 ms 7268 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 25.0

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

Subtask #4
0.0 / 15.0

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

Subtask #5
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 348 KB Output is correct
2 Runtime error 2 ms 860 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #6
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Runtime error 1 ms 604 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -