This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |