Submission #1179841

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179841		alexdd	Parking (CEOI22_parking)	C++20	10 / 100	77 ms	11956 KiB

Main

#include<bits/stdc++.h>
using namespace std;
int n,m;
int sus[200005],jos[200005];
                   ///0 - jos
                   ///1 - sus
                   ///2 - singur
pair<pair<int,int>,pair<int,int>> pozs[200005];///{poz,tip}
set<int> libere;
set<int> s[3][3];
void sort_car(int i)
{
    if(pozs[i].first.second > pozs[i].second.second)
        swap(pozs[i].first, pozs[i].second);
}
void scoate(int i)
{
    if(i==0)
        return;

    assert(pozs[i].first.first != 0);
    assert(pozs[i].second.first != 0);

    sort_car(i);

    s[pozs[i].first.second][pozs[i].second.second].erase(i);
}
void baga(int i)
{
    if(i==0)
        return;

    assert(pozs[i].first.first != 0);
    assert(pozs[i].second.first != 0);

    sort_car(i);

    if(pozs[i].first.first != pozs[i].second.first)
        s[pozs[i].first.second][pozs[i].second.second].insert(i);
}
int remove_car(int poz)
{
    assert(jos[poz]);
    if(sus[poz])
    {
        assert(jos[poz] != sus[poz]);

        int car = sus[poz];
        sus[poz] = 0;

        if(pozs[car].first.first == poz)
            swap(pozs[car].first, pozs[car].second);
        pozs[car].second = {0, -1};

        if(pozs[jos[poz]].second.first == poz)
            swap(pozs[jos[poz]].first, pozs[jos[poz]].second);
        pozs[jos[poz]].first = {poz, 2};

        return car;
    }
    else
    {
        int car = jos[poz];
        jos[poz] = 0;
        libere.insert(poz);


        if(pozs[car].first.first == poz)
            swap(pozs[car].first, pozs[car].second);
        pozs[car].second = {0, -1};

        return car;
    }
}
void add_car(int poz, int car)
{
    assert(sus[poz]==0);
    if(jos[poz]==0)
    {
        libere.erase(poz);
        jos[poz] = car;
        pozs[car].second = {poz, 2};
    }
    else
    {
        sus[poz] = car;
        pozs[car].second = {poz, 1};

        if(pozs[jos[poz]].second.first == poz)
            swap(pozs[jos[poz]].first, pozs[jos[poz]].second);
        pozs[jos[poz]].first = {poz, 0};
    }
}
vector<pair<int,int>> sol;
void move_car(int from, int to)
{
    assert(from);
    assert(to);

    scoate(jos[from]);
    scoate(sus[from]);
    scoate(jos[to]);
    scoate(sus[to]);

    int car = remove_car(from);
    add_car(to, car);

    sol.push_back({from, to});

    baga(jos[from]);
    baga(sus[from]);
    baga(jos[to]);
    baga(sus[to]);
}
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>jos[i]>>sus[i];
        if(jos[i]==0)
        {
            libere.insert(i);
        }
        else if(sus[i]==0)
        {
            if(pozs[jos[i]].first.first == 0)
                pozs[jos[i]].first = {i, 2};
            else
                pozs[jos[i]].second = {i, 2};
        }
        else
        {
            if(pozs[jos[i]].first.first == 0)
                pozs[jos[i]].first = {i, 0};
            else
                pozs[jos[i]].second = {i, 0};

            if(pozs[sus[i]].first.first == 0)
                pozs[sus[i]].first = {i, 1};
            else
                pozs[sus[i]].second = {i, 1};

        }
    }
    for(int i=1;i<=n;i++)
        baga(i);
    while(1)
    {
        if(!s[2][2].empty())
        {
            int car = *s[2][2].begin();

            move_car(pozs[car].first.first, pozs[car].second.first);
        }
        else if(!s[1][2].empty())
        {
            int car = *s[1][2].begin();

            move_car(pozs[car].first.first, pozs[car].second.first);
        }
        else if(!s[0][2].empty())
        {
            if(libere.empty())
            {
                cout<<-1;
                return 0;
            }
            int car = *s[0][2].begin();
            int poz = *libere.begin();
            sort_car(car);
            int p0 = pozs[car].first.first, p2 = pozs[car].second.first;
            move_car(p0, poz);
            move_car(p2, p0);
        }
        else if(!s[0][1].empty())
        {
            if(libere.empty())
            {
                cout<<-1;
                return 0;
            }
            int car = *s[0][1].begin();
            int poz = *libere.begin();
            sort_car(car);
            int p0 = pozs[car].first.first, p1 = pozs[car].second.first;
            move_car(p0, poz);
            move_car(p1, p0);
        }
        else if(!s[1][1].empty())
        {
            if(libere.empty())
            {
                cout<<-1;
                return 0;
            }
            int car = *s[1][1].begin();
            int poz = *libere.begin();
            int p0 = pozs[car].first.first, p1 = pozs[car].second.first;
            move_car(p0, poz);
            move_car(p1, poz);
        }
        else
        {
            break;
        }
    }

    for(int i=1;i<=m;i++)
        assert(jos[i]==sus[i]);

    cout<<(int)sol.size()<<"\n";
    for(auto [x,y]:sol)
        cout<<x<<" "<<y<<"\n";
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 25
• Subtask 4: 0 / 15
• Subtask 5: 0 / 25
• Subtask 6: 0 / 15