oj.uz

Submission #787729

# Submission time Handle Problem Language Result Execution time Memory
787729 2023-07-19T11:48:10 Z doowey Parking (CEOI22_parking) C++17
10 / 100
 2000 ms 10500 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)2e5 + 10;
vector<pii> P[N];
int park[N][2];
vector<pii> res;

int n, m;

void apply_operation(int x, int y){
    res.push_back(mp(x,y));
    int ci = 0;
    int cj = 0;
    if(park[x][ci] == 0) ci ++ ;
    if(park[y][cj+1] == 0) cj ++ ;
    // x -> y
    int id = park[x][ci];
    if(P[id][0] == mp(x, ci))
        P[id].erase(P[id].begin());
    else
        P[id].erase(P[id].begin() + 1);
    park[y][cj] = id;
    park[x][ci] = 0;
    P[id].push_back(mp(y, cj));
}

bool car_sort(){
    // Case 1:
    for(int it = 1; it <= n; it ++ ){
        if(P[it][0].fi == P[it][1].fi) continue;
        for(int j = 0 ; j < 2; j ++ ){
            if(P[it][j].se == 1 && P[it][(j^1)].se == 0 && park[P[it][j].fi][0] == 0){ // up is empty
                apply_operation(P[it][(j^1)].fi, P[it][j].fi);
                return true;
            }
        }
    }
    // Case 2:
    for(int it = 1; it <= n; it ++ ){
        if(P[it][0].fi == P[it][1].fi) continue;
        if(P[it][0].se == 1 && P[it][1].se == 1 && park[P[it][0].fi][0] == 0 && park[P[it][1].fi][0] == 0){
            apply_operation(P[it][0].fi, P[it][1].fi);
            return true;
        }
    }
    int emp = 0;
    for(int it = 1; it <= m; it ++ ){
        if(park[it][0] + park[it][1] == 0) {
            emp = it;
            break;
        }
    }
    if(!emp) return false;
    // Case 3:
    for(int it = 1; it <= n; it ++ ){
        if(P[it][0].fi == P[it][1].fi) continue;
        for(int j = 0 ; j < 2; j ++ ){
            if(P[it][j].se == 1 && P[it][(j^1)].se == 1 && park[P[it][j].fi][0] == 0){
                apply_operation(P[it][j^1].fi, emp);
                apply_operation(P[it][j].fi, P[it][j^1].fi);
                return true;
            }
        }
    }
    // Case 4:
    int rev;
    int pa, pb;
    for(int it = 1; it <= n; it ++ ){
        if(P[it][0].fi == P[it][1].fi) continue;
        if(P[it][0].se != P[it][1].se) continue;
        rev = (P[it][0].se ^ 1);
        pa = P[it][0].fi;
        pb = P[it][1].fi;
        if(park[pa][rev] == park[pb][rev]){
            apply_operation(pa, emp);
            apply_operation(pb, emp);
            apply_operation(pa, pb);
            return true;
        }
    }
    // Case 5:
    for(int it = 1; it <= n; it ++ ){
        if(P[it][0].fi == P[it][1].fi) continue;
        apply_operation(P[it][0].fi, emp);
        return true;
    }
    return false;
}

int main(){
    fastIO;
    //freopen("in.txt", "r", stdin);
    cin >> n >> m;
    int s, t;
    for(int i = 1; i <= m ; i ++ ){
        cin >> park[i][1] >> park[i][0];
        for(int j = 0 ; j < 2; j ++ ){
            if(park[i][j] > 0) P[park[i][j]].push_back(mp(i,j));
        }
    }
    while(car_sort());
    for(int i = 1; i <= m; i ++ ){
        if(park[i][0] != park[i][1]){
            cout << "-1\n";
            return 0;
        }
    }
    cout << res.size() << "\n";
    for(auto p : res){
        cout << p.fi << " " << p.se << "\n";
    }
    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:104:9: warning: unused variable 's' [-Wunused-variable]
  104 |     int s, t;
      |         ^
Main.cpp:104:12: warning: unused variable 't' [-Wunused-variable]
  104 |     int s, t;
      |            ^

Subtask #1
10.0 / 10.0

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

Subtask #2
0.0 / 10.0

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

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 5076 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 4 ms 5076 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 25.0

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

Subtask #6
0.0 / 15.0

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