Submission #1231192

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231192		Tenis0206	Parking (CEOI22_parking)	C++20	10 / 100	44 ms	11192 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int nmax = 2e5;

int n, m;
int b[nmax + 5], t[nmax + 5];

vector<pair<int,int>> l[nmax + 5];

int sel[nmax + 5];

int nr = 0;
int found = 0;
bool open = false;

vector<pair<int,int>> rez;

bool over(int a)
{
    if(l[a].front().second != 1 || l[a].back().second != 1)
    {
        return false;
    }
    return true;
}

void dfs(int nod, int poz, bool lvl)
{
    if(lvl == 0 && t[poz] == 0)
    {
        open = true;
    }
    if(over(nod) && sel[nod] == 0)
    {
        ++found;
    }
    if(!sel[nod])
    {
        ++nr;
    }
    ++sel[nod];
    if(sel[nod] == 1)
    {
        for(auto it : l[nod])
        {
            if(poz == it.first && lvl == it.second)
            {
                continue;
            }
            dfs(nod, it.first, it.second);
        }
    }
    if(lvl == 0)
    {
        if(t[poz] != 0 && !sel[t[poz]])
        {
            dfs(t[poz], poz, 1);
        }
    }
    else
    {
        if(b[poz] != 0  && !sel[b[poz]])
        {
            dfs(b[poz], poz, 0);
        }
    }
}

bool make_move_0()
{
    int val = 0;
    for(int i=1;i<=n;i++)
    {
        if(l[i].front().first == l[i].back().first)
        {
            continue;
        }
        if(l[i].front().second == 0 && !t[l[i].front().first] && l[i].back().second == 0 && !t[l[i].back().first])
        {
            val = i;
            break;
        }
    }
    if(val)
    {
        int poz = l[val].front().first;
        rez.push_back({l[val].back().first, poz});
        b[l[val].back().first] = 0;
        t[poz] = val;
        l[val].clear();
        l[val].push_back({poz, 0});
        l[val].push_back({poz, 1});
        return true;
    }
    int poz_from = 0, poz_to = 0;
    for(int i=1;i<=n;i++)
    {
        if(l[i].front().first == l[i].back().first)
        {
            continue;
        }
        if(l[i].front().second == 0 && !t[l[i].front().first] && l[i].back().second == 1)
        {
            val = i;
            poz_from = l[i].back().first;
            poz_to = l[i].front().first;
            break;
        }
        if(l[i].back().second == 0 && !t[l[i].back().first] && l[i].front().second == 1)
        {
            val = i;
            poz_from = l[i].front().first;
            poz_to = l[i].back().first;
            break;
        }
    }
    if(val)
    {
        rez.push_back({poz_from, poz_to});
        t[poz_from] = 0;
        t[poz_to] = val;
        l[val].clear();
        l[val].push_back({poz_to, 0});
        l[val].push_back({poz_to, 1});
        return true;
    }
    return false;
}

bool make_move_1()
{
    int poz_empty = 0;
    for(int i=1;i<=m;i++)
    {
        if(!b[i])
        {
            poz_empty = i;
            break;
        }
    }
    if(!poz_empty)
    {
        return false;
    }

    int poz = 0;
    int val = 0;
    for(int i=1;i<=n;i++)
    {
        if(l[i].front().first == l[i].back().first)
        {
            continue;
        }
        if(l[i].front().second == 0 && !t[l[i].front().first] && l[i].back().second == 0 && l[t[l[i].back().first]].front().second == 1 && l[t[l[i].back().first]].back().second == 1)
        {
            val = t[l[i].back().first];
            poz = l[i].back().first;
            break;
        }
        if(l[i].back().second == 0 && !t[l[i].back().first] && l[i].front().second == 0 && l[t[l[i].front().first]].front().second == 1 && l[t[l[i].front().first]].back().second == 1)
        {
            val = t[l[i].front().first];
            poz = l[i].front().first;
            break;
        }
    }
    if(val)
    {
        rez.push_back({poz, poz_empty});
        t[poz] = 0;
        b[poz_empty] = val;
        for(int i=0;i<2;i++)
        {
            if(l[val][i].first == poz)
            {
                l[val][i].first = poz_empty;
                l[val][i].second = 0;
                break;
            }
        }
        return true;
    }
    for(int i=1;i<=n;i++)
    {
        if(l[i].front().first == l[i].back().first)
        {
            continue;
        }
        if(l[i].front().second == 1 && l[i].back().second == 0 && l[t[l[i].back().first]].front().second == 1 && l[t[l[i].back().first]].back().second == 1)
        {
            val = t[l[i].back().first];
            poz = l[i].back().first;
            break;
        }
        if(l[i].back().second == 1 && l[i].front().second == 0 && l[t[l[i].front().first]].front().second == 1 && l[t[l[i].front().first]].back().second == 1)
        {
            val = t[l[i].front().first];
            poz = l[i].front().first;
            break;
        }
    }
    if(val)
    {
        rez.push_back({poz, poz_empty});
        t[poz] = 0;
        b[poz_empty] = val;
        for(int i=0;i<2;i++)
        {
            if(l[val][i].first == poz)
            {
                l[val][i].first = poz_empty;
                l[val][i].second = 0;
                break;
            }
        }
        return true;
    }

    for(int i=1;i<=n;i++)
    {
        if(l[i].front().first == l[i].back().first)
        {
            continue;
        }
        if(l[i].front().second == 0 && l[i].back().second == 0 && t[l[i].front().first] == t[l[i].back().first])
        {
            val = t[l[i].back().first];
            poz = l[i].back().first;
            break;
        }
    }
    if(val)
    {
        rez.push_back({poz, poz_empty});
        t[poz] = 0;
        b[poz_empty] = val;
        for(int i=0;i<2;i++)
        {
            if(l[val][i].first == poz)
            {
                l[val][i].first = poz_empty;
                l[val][i].second = 0;
                break;
            }
        }
        return true;
    }

    for(int i=1;i<=n;i++)
    {
        if(l[i].front().first == l[i].back().first)
        {
            continue;
        }
        if(l[i].front().second == 0 && !t[l[i].front().first] && l[i].back().second == 0)
        {
            val = t[l[i].back().first];
            poz = l[i].back().first;
            break;
        }
        if(l[i].back().second == 0 && !t[l[i].back().first] && l[i].front().second == 0)
        {
            val = t[l[i].front().first];
            poz = l[i].front().first;
            break;
        }
    }
    if(val)
    {
        rez.push_back({poz, poz_empty});
        t[poz] = 0;
        b[poz_empty] = val;
        for(int i=0;i<2;i++)
        {
            if(l[val][i].first == poz)
            {
                l[val][i].first = poz_empty;
                l[val][i].second = 0;
                break;
            }
        }
        return true;
    }
    for(int i=1;i<=n;i++)
    {
        if(l[i].front().first == l[i].back().first)
        {
            continue;
        }
        if(l[i].front().second == 1 && l[i].back().second == 0)
        {
            val = t[l[i].back().first];
            poz = l[i].back().first;
            break;
        }
        if(l[i].back().second == 1 && l[i].front().second == 0)
        {
            val = t[l[i].front().first];
            poz = l[i].front().first;
            break;
        }
    }
    if(val)
    {
        rez.push_back({poz, poz_empty});
        t[poz] = 0;
        b[poz_empty] = val;
        for(int i=0;i<2;i++)
        {
            if(l[val][i].first == poz)
            {
                l[val][i].first = poz_empty;
                l[val][i].second = 0;
                break;
            }
        }
        return true;
    }

    return false;
}

bool make_move_2()
{
    int poz_empty = 0;
    for(int i=1;i<=m;i++)
    {
        if(!b[i])
        {
            poz_empty = i;
            break;
        }
    }
    if(!poz_empty)
    {
        return false;
    }

    int val = 0;
    int poz1 = 0, poz2 = 0;
    for(int i=1;i<=n;i++)
    {
        if(l[i].front().first == l[i].back().first)
        {
            continue;
        }
        if(l[i].front().second == 1 && l[i].back().second == 1)
        {
            val = i;
            poz1 = l[i].front().first;
            poz2 = l[i].back().first;
            break;
        }
    }
    if(val)
    {
        rez.push_back({poz1, poz_empty});
        rez.push_back({poz2, poz_empty});
        t[poz1] = t[poz2] = 0;
        b[poz_empty] = t[poz_empty] = val;
        l[val].clear();
        l[val].push_back({poz_empty, 0});
        l[val].push_back({poz_empty, 1});
        return true;
    }

    return false;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
#ifdef home
    freopen("nr.in","r",stdin);
    freopen("nr.out","w",stdout);
#endif // home
    cin>>n>>m;
    bool done = true;
    for(int i=1; i<=m; i++)
    {
        cin>>b[i]>>t[i];
        l[b[i]].push_back({i, 0});
        l[t[i]].push_back({i, 1});
        if(t[i] != b[i])
        {
            done = false;
        }
    }
    if(n == m && !done)
    {
        cout<<-1<<'\n';
        return 0;
    }
    if(n > 1000)
    {
        bool ok = false;
        int rez = 0;
        for(int i=1; i<=m; i++)
        {
            nr = 0;
            found = 0;
            open = false;
            if(t[i] != 0 && !sel[t[i]])
            {
                dfs(t[i], i, 1);
            }
            else if(b[i] != 0 && !sel[b[i]])
            {
                dfs(b[i], i, 0);
            }
            if(nr <= 1)
            {
                continue;
            }
            rez += (nr + (found > 1) * (found - 1) + 1);
            if(found > 1)
            {
                ok = true;
            }
        }
        if(ok && m == n + 1)
        {
            cout<<-1<<'\n';
            return 0;
        }
        cout<<rez<<'\n';
        return 0;
    }
    while(true)
    {
        int cnt_left = 0;
        for(int i=1;i<=n;i++)
        {
            if(l[i].front().first == l[i].back().first)
            {
                continue;
            }
            ++cnt_left;
        }
        if(cnt_left == 0)
        {
            break;
        }
        if(make_move_0())
        {
            continue;
        }
        if(make_move_1())
        {
            continue;
        }
        if(make_move_2())
        {
            continue;
        }
        cout<<-1<<'\n';
        return 0;
    }
    cout<<rez.size()<<'\n';
    for(auto it : rez)
    {
        cout<<it.first<<' '<<it.second<<'\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