oj.uz

Submission #1097853

# Submission time Handle Problem Language Result Execution time Memory
1097853 2024-10-08T11:18:38 Z gyg Parking (CEOI22_parking) C++17
10 / 100
 2000 ms 9316 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, 2 * 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);
    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() {
    while (true) {
        if (fn()) break;

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

        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 << "FINAL" << endl;
        //     for (pii x : ans) cout << x.fir << " " << x.sec << endl;
        // }
        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 <= 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), freopen("prk.out", "w", stdout);
    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 2396 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 0 ms 2392 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2392 KB Output is correct
6 Correct 1 ms 2392 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2392 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2064 ms 9316 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 2396 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 2396 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 3 ms 2396 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 3 ms 2396 KB Output is correct
4 Correct 2 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 3 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Incorrect 1 ms 2396 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 2396 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 0 ms 2392 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2392 KB Output is correct
6 Correct 1 ms 2392 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2392 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Execution timed out 2064 ms 9316 KB Time limit exceeded
12 Halted 0 ms 0 KB -