Submission #787833

#	Time	Username	Problem	Language	Result	Execution time	Memory
787833		doowey	Parking (CEOI22_parking)	C++17	2 / 100	48 ms	14256 KiB

Main

#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 pt[N];

int n, m;

set<int> empt;
set<int> C[6];

int get_case(int it){
    if(P[it][0].fi == P[it][1].fi) return -1;
    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){
            return 0;
        }
    }
    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){
        return 1;
    }
    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){
            return 2;
        }
    }
    int rev;
    int pa, pb;
    if(P[it][0].se != P[it][1].se){
        rev = (P[it][0].se ^ 1);
        pa = P[it][0].fi;
        pb = P[it][1].fi;
        if(park[pa][rev] == park[pb][rev]){
            return 3;
        }
    }
    if(P[it][0].se == 1 && P[it][1].se == 1){
        return 4;
    }
    return 5;
}

void apply_operation(int x, int y){
    res.push_back(mp(x,y));
    int ci = 0;
    int cj = 0;
    if(empt.count(x)) empt.erase(x);
    if(empt.count(y)) empt.erase(y);
    if(park[x][ci] == 0) ci ++ ;
    if(park[y][cj+1] == 0) cj ++ ;
    set<int> E;
    for(int j = 0 ; j < 2; j ++ ){
        if(park[x][j] != 0) E.insert(park[x][j]);
        if(park[y][j] != 0) E.insert(park[y][j]);
    }
    int c;
    for(auto x : E){
        c = get_case(x);
        if(c >= 0) C[c].erase(x);
    }
    // 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));
    if(park[x][0] + park[x][1] == 0) empt.insert(x);
    if(park[y][0] + park[y][1] == 0) empt.insert(y);
    for(auto x : E){
        c = get_case(x);
        if(c >= 0) C[c].insert(x);
    }
}


bool car_sort(){
    // Case 1:
    int it;
    if(!C[0].empty()){
        it = *C[0].begin();
        cout << "Case 0: \n";
        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:
    if(!C[1].empty()){
        it = *C[1].begin();
        apply_operation(P[it][0].fi, P[it][1].fi);
        cout << "Case 1: \n";
        return true;
    }
    if(empt.empty()) return false;
    int emp = *empt.begin();
    // Case 3:
    if(!C[2].empty()){
        it = *C[2].begin();
        cout << "Case 2: \n";
        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;
    if(!C[3].empty()){
        it = *C[3].begin();
        cout << "Case 3: \n";
        rev = (P[it][0].se ^ 1);
        pa = P[it][0].fi;
        pb = P[it][1].fi;
        apply_operation(pa, emp);
        apply_operation(pb, emp);
        apply_operation(pa, pb);
        return true;
    }
    // Case 5:
    if(!C[4].empty()){
        it = *C[4].begin();
        cout << "Case 4: \n";
        apply_operation(P[it][0].fi, emp);
        return true;
    }
    if(!C[5].empty()){
        it = *C[5].begin();
        cout << "Case 5: \n";
        apply_operation(P[it][0].fi, emp);
        return true;
    }
    return false;
}

vector<array<int,2>> pp;
set<vector<array<int,2>>> G;


int solve(){
    for(int i = 1; i <= m; i ++ ){
        pp.push_back({park[i][0], park[i][1]});
    }
    queue<vector<array<int,2>>> que;
    map<vector<array<int,2>>, int> res;
    que.push(pp);
    res[pp]=0;
    int d;
    int ci;
    while(!que.empty()){
        pp=que.front();
        que.pop();
        bool good = true;
        for(int i = 0; i < m ; i ++ ){
            if(pp[i][0] != pp[i][1]){
                good = false;
            }
        }
        d=res[pp];
        if(good){
            return d;
        }
        int t1;
        int t2;
        //return;
        /*
        for(int i = 0 ; i < m ; i ++ ){
            cout << pp[i][0] << " ";
        }
        cout << "|\n";
        for(int i = 0 ; i < m ; i ++ ){
            cout << pp[i][1] << " ";
        }
        cout << "|\n";
        cout << "-------------\n";
        */
        for(int i = 0; i < m; i ++ ){
            if(pp[i][0] == pp[i][1]) continue; // dont move it
            t1 = 0;
            if(pp[i][0] == 0) t1 = 1;
            ci = 0;
            for(int j = 0; j < m ; j ++ ){
                if(j == i) continue;
                if(pp[j][0] != 0) continue;
                if(pp[j][1] == 0) t2 = 1;
                else t2 = 0;
                if(t2 == 0 && pp[i][t1] != pp[j][t2 + 1]) continue;
                if(pp[j][0] + pp[j][1] == 0) {
                    if(pp[i][0] == 0) continue;
                    ci ++ ;
                    if(ci == 2) continue;
                }
                pp[j][t2]=pp[i][t1];
                pp[i][t1]=0;
                if(!res.count(pp)){
                    res[pp]=d+1;
                    que.push(pp);
                }
                pp[i][t1]=pp[j][t2];
                pp[j][t2]=0;
            }
        }
    }
    return -1;
}

int main(){
    fastIO;
    //freopen("in.txt", "r", stdin);
    cin >> n >> m;
    int v;
    int est = 0;
    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));
        }
        if(park[i][0] + park[i][1] == 0) empt.insert(i);
    }
    for(int i = 1; i <= n; i ++) {
        if(P[i][0].se == 0 && P[i][1].se == 0) est += 2;
        else if(P[i][0].fi != P[i][1].fi) est ++ ;
    }
    cout << est << "\n";
    return 0;
    for(int i = 1; i <= n ; i ++ ){
        int v = get_case(i);
        if(v >= 0){
            C[v].insert(i);
        }
    }
    int s = solve();
    cout << "comp: " << s << "\n";
    for(int i = 1; i <= m ; i ++ ){
        cout << park[i][0] << " ";
    }
    cout << "|\n";
    for(int i = 1; i <= m ; i ++ ){
        cout << park[i][1] << " ";
    }
    cout << "|\n";
    cout << "----------\n";
    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 (stderr)

Main.cpp: In function 'bool car_sort()':
Main.cpp:126:9: warning: variable 'rev' set but not used [-Wunused-but-set-variable]
  126 |     int rev;
      |         ^~~
Main.cpp: In function 'int main()':
Main.cpp:230:9: warning: unused variable 'v' [-Wunused-variable]
  230 |     int v;
      |         ^

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