Submission #782344

#TimeUsernameProblemLanguageResultExecution timeMemory
782344OzyParking (CEOI22_parking)C++17
10 / 100
64 ms24128 KiB
#include <iostream> #include <bits/stdc++.h> using namespace std; #define lli long long int #define debug(a) cout << #a << " = " << a << endl #define debugsl(a) cout << #a << " = " << a << ", " #define rep(i,a,b) for(int i = (a); i <= (b); i++) #define repa(i,a,b) for(int i = (a); i >= (b); i--) #define pll pair<lli,lli> #define MAX 200000 lli n,m,b,t; lli estacionamiento[(MAX*2)+2][2], ya[MAX+2]; vector<lli> activos[MAX+2][2]; vector<lli> down,up,vacios; vector<pll> res; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n >> m; rep(i,1,m) { cin >> estacionamiento[i][0] >> estacionamiento[i][1]; if (estacionamiento[i][1] != 0) { if(estacionamiento[i][1] == estacionamiento[i][0]) continue; up.push_back(i); activos[estacionamiento[i][1]][1].push_back(i); continue; } if (estacionamiento[i][0] != 0) { down.push_back(i); activos[estacionamiento[i][0]][0].push_back(i); continue; } vacios.push_back(i); } rep(i,1,n) { if (activos[i][1].size() < 2) continue; lli a = vacios[ vacios.size()-1 ]; vacios.pop_back(); res.push_back({activos[i][1][0],a}); res.push_back({activos[i][1][1],a}); ya[estacionamiento[ activos[i][1][1] ][1]] = 1; //acitva los menores a = estacionamiento[ activos[i][1][1] ][0]; lli b = estacionamiento[ activos[i][1][0] ][0]; activos[a][0].push_back(activos[i][1][1]); activos[b][0].push_back(activos[i][1][0]); activos[i][1].clear(); } for(auto u : up) { lli val = estacionamiento[u][1]; if (ya[val]) continue; if(activos[ val ][1].size() == 1 && activos[ val ][0].size() == 1) { res.push_back({activos[val][1][0], activos[val][0][0]}); ya[val] = 1; //activa el de abajo val = estacionamiento[u][0]; if (ya[val] == 1) continue; activos[val][0].push_back(u); while (activos[ val ][1].size() == 1 && activos[ val ][0].size() == 1) { res.push_back({activos[val][1][0], activos[val][0][0]}); ya[val] = 1; //activa el de abajo lli x = activos[val][1][0]; val = estacionamiento[ x ][0]; if (ya[val] == 1) break; activos[val][0].push_back(x); } } } //checa por si quedo algun grande for(auto u : up) { lli val = estacionamiento[u][1]; if (ya[val]) continue; lli v = vacios[vacios.size()-1]; vacios.pop_back(); res.push_back({activos[val][1][0], v}); activos[val][0].push_back(v); //activa el de abajo val = estacionamiento[u][0]; if (ya[val] == 1) continue; activos[val][0].push_back(u); while (activos[ val ][1].size() == 1 && activos[ val ][0].size() == 1) { res.push_back({activos[val][1][0], activos[val][0][0]}); ya[val] = 1; //activa el de abajo lli x = activos[val][1][0]; val = estacionamiento[ x ][0]; if (ya[val] == 1) break; activos[val][0].push_back(x); } } rep(i,1,n) { //debugsl(i); //debug(activos[i][0].size()); if(activos[i][0].size() == 2) { res.push_back({activos[i][0][0], activos[i][0][1]}); } } cout << res.size() << "\n"; for(auto r : res) cout << r.first << ' ' << r.second << "\n"; return 0; }
#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...