Submission #1157474

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157474		ace5	Parking (CEOI22_parking)	C++20	100 / 100	414 ms	20680 KiB

Main

#include <bits/stdc++.h>

using namespace std;

//0 - done
//1 - two second free (can be done in 1 move)
//2 - two second one free
//3 - two blocked second
//4 - one free second one first (can be done in 1 move)
//5 - one blocked second one first
//6 - two firsts

struct place
{
    place(){i = -1;s = 0;};
    place(int _i,bool _s){i = _i;s = _s;};
    int i;
    bool s;
    bool operator == (const place & oth){return i == oth.i && s == oth.s;};
    //0 - first
    //1 - second
};

const int maxn = 200005;

int type[maxn];
bool ise[maxn];
vector<pair<int,int>> ans;
vector<set<int>> f(7);
set<int> empty_slots;
pair<place,place> col[maxn];
int slot[maxn][2];

int get_type(pair<place,place> c)
{
    //cout << c.first.i << ' ' << c.second.i << ' ';
    if(c.first.s)
    {
        swap(c.first,c.second);
    }
    if(c.first.i == c.second.i)
    {
        return 0;
    }
    else if(!c.first.s && !c.second.s)
    {
        int k = int(slot[c.first.i][1] == -1) + int(slot[c.second.i][1] == -1);
        return (k == 0 ? 3 : (k == 1 ? 2 : 1));
    }
    else if(!c.first.s)
    {
        return (slot[c.first.i][1] == -1 ? 4 : 5);
    }
    else
    {
        return 6;
    }
}

void upd_col_type(int i)
{
    f[type[i]].erase(i);
    pair<place,place> c = col[i];
   // cout << c.first.i << ' ' << c.first.s << ' ' << c.second.i << ' ' << c.second.s << endl;
    type[i] = get_type(c);
    f[type[i]].insert(i);
}
void upd_slot(int i)
{
    if(ise[i])
        empty_slots.erase(i);
    if(slot[i][0] == -1 && slot[i][1] == -1)
    {
        ise[i] = 1;
    }
    else
        ise[i] = 0;
    if(slot[i][0] != -1)
        upd_col_type(slot[i][0]);
    if(slot[i][1] != -1)
        upd_col_type(slot[i][1]);
    if(ise[i])
        empty_slots.insert(i);
}
bool move_to(place a,place b)
{
    if(slot[b.i][b.s] != -1 || slot[a.i][a.s] == -1 || (b.s == 0 && slot[b.i][1] != -1) || (a.s == 0 && slot[a.i][1] != -1))
        return false;
    else
    {
        ans.push_back({a.i,b.i});
        if(col[slot[a.i][a.s]].first == a)
            col[slot[a.i][a.s]].first = b;
        else
            col[slot[a.i][a.s]].second = b;
        swap(slot[b.i][b.s],slot[a.i][a.s]);
        upd_slot(a.i);
        upd_slot(b.i);
        return true;
    }
}
bool process()
{
    while(true)
    {
        //cout << f[2].size() << endl;
        if(f[1].size())
        {
            //cout << "!" << endl;
            int x = *f[1].begin();
            int u = f[0].size();
            assert(move_to(col[x].first,{col[x].second.i,1}));
            assert(u != f[0].size());
        }
        else if(f[4].size())
        {
            //cout << "!" << endl;
            int x = *f[4].begin();
            if(col[x].first.s == 1)
                swap(col[x].first,col[x].second);
            int u = f[0].size();
            assert(move_to(col[x].second,place(col[x].first.i,1)));
            assert(u != f[0].size());
        }
        else if(f[2].size())
        {
            //cout << "!" << endl;
            int x = *f[2].begin();
            //cout << x << ' ';
            if(slot[col[x].first.i][1] == -1)
            {
                swap(col[x].first,col[x].second);
            }
            while(type[x] != 6)
            {
                if(slot[col[x].first.i][1] == x)
                {
                    swap(col[x].first,col[x].second);
                }
                x = slot[col[x].first.i][1];
            }
            if(!empty_slots.size())
            {
                return false;
            }
            else
            {
                int i = *empty_slots.begin();
               // cout << i << ' ';
               // cout << slot[col[x].first.i][col[x].first.s] << ' ';
                assert(move_to(col[x].first,place(i,0)));
                assert(move_to(col[x].second,place(i,1)));
               // cout << type[x] << endl;
            }
        }
        else if(f[6].size())
        {
            int x = *f[6].begin();
            if(!empty_slots.size())
            {
                return false;
            }
            else
            {
                int i = *empty_slots.begin();
                assert(move_to(col[x].first,place(i,0)));
                assert(move_to(col[x].second,place(i,1)));
            }
        }
        else if(f[5].size())
        {
            int x = *f[5].begin();
            if(slot[col[x].first.i][0] == x)
            {
                swap(col[x].first,col[x].second);
            }
            if(!empty_slots.size())
            {
                return false;
            }
            else
            {
                int i = *empty_slots.begin();
                assert(move_to(col[x].first,place(i,0)));
            }
        }
        else
            break;
    }
    return true;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n,m;
    cin >> n >> m;
    for(int i = 0;i < m;++i)
    {
        int a,b;
        cin >> a >> b;
        a--;
        b--;
        slot[i][1] = b;
        slot[i][0] = a;
        if(a+b == -2)
        {
            ise[i] = 1;
            empty_slots.insert(i);
        }
        if(a != -1)
        {
            if(col[a].first.i == -1)
                col[a].first = place(i,0);
            else
                col[a].second = place(i,0);
        }
        if(b != -1)
        {
            if(col[b].first.i == -1)
                col[b].first = place(i,1);
            else
                col[b].second = place(i,1);
        }
    }

    for(int i = 0;i < n;++i)
    {
        type[i] = get_type({col[i].first,col[i].second});
        //cout << type[i] << ' ';
        f[type[i]].insert(i);
    }
   // cout << slot[col[4].first.i][col[4].first.s] << "\n";
    if(process())
    {
        cout << ans.size() << "\n";
        for(int j = 0;j < ans.size();++j)
        {
            cout << ans[j].first+1 << ' ' << ans[j].second+1 << endl;
        }
    }
    else
        cout << -1 << "\n";
    return 0;
}

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