Submission #787833

#TimeUsernameProblemLanguageResultExecution timeMemory
787833dooweyParking (CEOI22_parking)C++17
2 / 100
48 ms14256 KiB
#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;
      |         ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...