oj.uz

Submission #782344

# Submission time Handle Problem Language Result Execution time Memory
782344 2023-07-13T20:32:26 Z Ozy Parking (CEOI22_parking) C++17
10 / 100
 64 ms 24128 KB 
#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;
}

Subtask #1
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9720 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 5 ms 9724 KB Output is correct
4 Runtime error 13 ms 19412 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 22568 KB Output is correct
2 Correct 64 ms 24128 KB Output is correct
3 Correct 44 ms 19952 KB Output is correct
4 Correct 44 ms 19524 KB Output is correct
5 Correct 62 ms 24016 KB Output is correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Partially correct 5 ms 9812 KB Output is partially correct
2 Correct 5 ms 9752 KB Output is correct
3 Runtime error 12 ms 19584 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #4
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Partially correct 5 ms 9812 KB Output is partially correct
2 Correct 5 ms 9752 KB Output is correct
3 Runtime error 12 ms 19584 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #5
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Partially correct 5 ms 9812 KB Output is partially correct
2 Incorrect 5 ms 9812 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9720 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 5 ms 9724 KB Output is correct
4 Runtime error 13 ms 19412 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -