제출 #1239434

#제출 시각아이디문제언어결과실행 시간메모리
1239434tapilyocaParking (CEOI22_parking)C++20
20 / 100
348 ms23536 KiB
/*********************************************** * auth: tapilyoca * * date: 07/13/2025 at 15:50:36 * * dots: https://github.com/tapilyoca/dotilyoca * ***********************************************/ #include <bits/stdc++.h> using namespace std; const long long MOD = 1e9+7; template<typename T> using vec = vector<T>; using ll = int; using vll = vec<ll>; using vvll = vec<vll>; using pll = pair<ll,ll>; using str = string; #define pb push_back #define dbg(x) if(1) cerr << #x << ": " << x << endl; /***********************************************/ struct ParkingSpot { ll topCar, botCar; ll sz; ParkingSpot(ll x, ll y) { if(x == 0) { topCar = botCar = sz = 0; } else if(y == 0) { topCar = x; sz = 1; botCar = 0; } else { topCar = y; botCar = x; sz = 2; } } ParkingSpot() : topCar(0), botCar(0), sz(0) {} void push_car(ll c) { assert(sz < 2); botCar = topCar; topCar = c; sz++; } ll pop_top() { ll temp = topCar; topCar = botCar; botCar = 0; sz--; return temp; } void print() { cerr << topCar << " " << botCar << endl; } }; vec<ParkingSpot> parking; map<ll,set<ll>> topCarToSpot; queue<ll> free_colors, almost_free_colors; vec<pll> output; queue<ll> empties; void drive_car(ll from, ll to) { // cerr << "Driving " << from << " to " << to << endl; if(parking[from].sz == 0) { cerr << "WHAT THE HELL ARE YOU DOING" << endl; assert(0); } if(parking[to].sz == 2) { cerr << "CANT PUSH CAR HERE, " << to << " FULL" << endl; assert(0); } topCarToSpot[parking[from].topCar].erase(from); topCarToSpot[parking[from].topCar].insert(to); parking[to].push_car(parking[from].pop_top()); // update our sets if(parking[from].sz == 0) { empties.push(from); } else { ll ccar = parking[from].topCar; topCarToSpot[ccar].insert(from); if(topCarToSpot[ccar].size() == 2) { if(parking[*topCarToSpot[ccar].begin()].sz + parking[*topCarToSpot[ccar].rbegin()].sz < 4) { free_colors.push(ccar); } else { almost_free_colors.push(ccar); } } } output.pb({from,to}); } void drive_car_2(ll from, ll to) { // cerr << "Mriving " << from << " " << to << endl; parking[to].push_car(parking[from].pop_top()); output.pb({from,to}); } void bruh(queue<ll> q) { while(!q.empty()) { cerr << q.front() << " "; q.pop(); } } void solve() { ll n, m; cin >> n >> m; parking.resize(m); for(int i = 0; i < m; i++) { ll x, y; cin >> x >> y; parking[i] = {x,y}; } for(int i = 0; i < m; i++) { if(parking[i].sz == 0) { empties.push(i); continue; } ll car = parking[i].topCar; if(car) topCarToSpot[car].insert(i); if(topCarToSpot[car].size() == 2) { // cerr << car << ": " << *topCarToSpot[car].begin() << " " << *topCarToSpot[car].rbegin() << endl; // check if this can be a free move if(parking[*topCarToSpot[car].begin()].sz + parking[*topCarToSpot[car].rbegin()].sz < 4) { free_colors.push(car); } else { almost_free_colors.push(car); } } } // cerr << "Free colors: "; // bruh(free_colors); // cerr << "\nAlmost free colors: "; // bruh(almost_free_colors); // cerr << endl; while(!free_colors.empty() or (!almost_free_colors.empty() and !empties.empty())) { if(!free_colors.empty()) { ll car = free_colors.front(); free_colors.pop(); if(parking[*topCarToSpot[car].begin()].sz == 2) { drive_car(*topCarToSpot[car].begin(), *topCarToSpot[car].rbegin()); } else { drive_car(*topCarToSpot[car].rbegin(), *topCarToSpot[car].begin()); } } if(!almost_free_colors.empty()) { ll car = almost_free_colors.front(); almost_free_colors.pop(); ll empty_spot = empties.front(); empties.pop(); parking[empty_spot] = {car, car}; ll f1 = *topCarToSpot[car].begin(), f2 = *topCarToSpot[car].rbegin(); parking[f1].pop_top(); parking[f2].pop_top(); output.pb({f1, empty_spot}); output.pb({f2, empty_spot}); if(parking[f1].sz == 0) empties.push(f1); else { ll f1c = parking[f1].topCar; topCarToSpot[f1c].insert(f1); if(topCarToSpot[f1c].size() == 2) { if(parking[*topCarToSpot[f1c].begin()].sz + parking[*topCarToSpot[f1c].rbegin()].sz < 4) { free_colors.push(f1c); } else { almost_free_colors.push(f1c); } } } if(parking[f2].sz == 0) empties.push(f2); else { ll f2c = parking[f2].topCar; topCarToSpot[f2c].insert(f2); if(topCarToSpot[f2c].size() == 2) { if(parking[*topCarToSpot[f2c].begin()].sz + parking[*topCarToSpot[f2c].rbegin()].sz < 4) { free_colors.push(f2c); } else { almost_free_colors.push(f2c); } } } // drive_car(*topCarToSpot[car].begin(), empty_spot); // drive_car(*topCarToSpot[car].rbegin(), empty_spot); } } if(!almost_free_colors.empty() and empties.empty()) { cout << -1 << endl; return; } // cerr << "Ok done with that now doing cycles" << endl; map<ll,ll> carToTopPosn; for(int i = 0; i < m; i++) { carToTopPosn[parking[i].topCar] = i; } for(int i = 0; i < m; i++) { if(parking[i].topCar == parking[i].botCar or parking[i].topCar == 0) continue; if(empties.empty()) { cout << -1 << endl; return; } // fix this cycle ll curr = i; // dbg(i); ll emptySlot = empties.front(); empties.pop(); drive_car_2(i,emptySlot); do { ll former = curr; curr = carToTopPosn[parking[curr].topCar]; // cerr << "f/c: " << former << " " << curr << endl; if(curr == i) { drive_car_2(former,emptySlot); empties.push(curr); break; } else { drive_car_2(curr,former); } } while(curr != i); // cerr << "Done with " << i << " heres parking: " << endl; // for(int i = 0; i < m; i++) { // cerr << parking[i].botCar << " " << parking[i].topCar << endl; // } } cout << output.size() << endl; for(auto[x,y] : output) cout << x+1 << " " << y+1 << endl; } int main() { ios::sync_with_stdio(false); cin.tie(NULL); int t = 1; while(t--) { solve(); } return 0; } /* 0 1 2 3 4 X 1 2 3 4 0 X 0 1 3 3 4 0 0 1 2 2 4 5 5 0 1 0 3 3 4 0 0 1 2 2 4 5 5 0 1 0 0 3 4 0 0 1 2 2 4 5 5 3 1 0 0 3 4 0 0 1 2 2 4 5 5 3 */
#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...