oj.uz

Submission #1097355

# Submission time Handle Problem Language Result Execution time Memory
1097355 2024-10-07T02:06:33 Z gyg Parking (CEOI22_parking) C++17
10 / 100
 2000 ms 7520 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;
}
bool tp(int i) { return (ps[i].sec == 1 || vl[ps[i].fir][1] == 0); }

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

    // Issue: falsly reporting impossible
    while (true) {
        // for (int i = 1; i <= m; i++) {
        //     cout << vl[i][0] << " " << vl[i][1] << endl;
        // }
        // cout << endl;

        if (fn()) break;

        bool flg = false;
        for (int i = 1; i <= 2 * n; i++) {
            int j = ps[i].fir;
            if (vl[j][1] == 0 && tp(fr(i))) {
                mv(ps[fr(i)].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; exit(0); }


        for (int i = 1; i <= 2 * n; i++) {
            if (ps[i].sec == 1 && ps[fr(i)].sec == 1 && vl[ps[i].fir][0] == vl[ps[fr(i)].fir][0]) {
                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[fr(i)].sec == 1 && tp(fr(vl[ps[i].fir][0]) && tp(fr(vl[ps[fr(i)].fir][0]))) ) {
                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[fr(i)].sec == 1 && (tp(fr(vl[ps[i].fir][0]) || tp(fr(vl[ps[fr(i)].fir][0])))) ) {
                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[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;
            }
        }
    }
}

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct

Subtask #2
0.0 / 10.0

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

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 3 ms 344 KB Output is correct
4 Correct 3 ms 448 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 3 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Incorrect 1 ms 344 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #6
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Execution timed out 2041 ms 7520 KB Time limit exceeded
12 Halted 0 ms 0 KB -