제출 #1236797

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1236797		amine_aroua	Parking (CEOI22_parking)	C++20	10 / 100	1953 ms	6208 KiB

Main

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
void apply_op(int i , int j , vector<int> &t , vector<int> &b , vector<pair<int ,int>> &ops)
{   
    int whati = 1; // top
    if(t[i] == 0)
        whati = 0;
    int whatj = 1;
    if(b[j] == 0)
        whatj = 0;
    swap((whati ? t[i] : b[i]) , (whatj ? t[j] : b[j]));
}   
signed main()
{
    int n , m;
    cin>>n>>m;
    vector<int> t(m) , b(m);
    vector<pair<int ,int>> ops;
    for(int i = 0 ; i < m ; i++)
    {
        cin>>b[i]>>t[i];
    }
    while(1.0 * clock() / CLOCKS_PER_SEC < 1.95)
    {
        bool barra = 0;
        for(int i = 0 ; i < m ; i++)
        {
            if(t[i] != b[i])
            {
                barra = 1;
                break;
            }
        }
        if(!barra)
            break;
        vector<vector<pair<int , int>>> v(n + 1);
        int emp = -1;
        for(int  i = 0 ; i < m ; i++)
        {
            if(b[i] == 0)
                emp = i;
            else
            {
                if(b[i] == t[i])
                    continue;
                if(t[i])
                    v[t[i]].push_back({1 , i});
                v[b[i]].push_back({0 , i});
            }
        }
        bool check = 0;
        for(int i = 1 ; i <= n ; i++)
        {
            if((int)v[i].size() == 2)
            {
                sort(v[i].begin() , v[i].end());
                if(v[i][0].first == 0)
                {
                    int idx1 = v[i][0].second;
                    int idx2 = v[i][1].second;
                    if(t[idx1] == 0)
                    {
                        if(v[i][1].first == 1 || t[idx2] == 0)
                        {
                            ops.push_back({idx2 , idx1});
                            v[i].clear();
                            apply_op(idx2 , idx1 , t , b , ops);
                            check = 1;
                            break;
                        }
                    }
                }
            }
        }
        if(check)
            continue;
        if(emp != -1)
        {
            for(int i = 1 ; i <= n ; i++)
            {
                if((int)v[i].size() == 2)
                {
                    sort(v[i].begin() , v[i].end());
                    if(v[i][0].first == 1)
                    {
                        int idx1 = v[i][0].second;
                        int idx2 = v[i][1].second;
                        ops.push_back({idx1 , emp});
                        ops.push_back({idx2 , emp});
                        apply_op(idx1 , emp , t , b , ops);
                        apply_op(idx2 , emp , t , b , ops);
                        check = 1;
                        break;
                    }
                }
            }
        }
        if(check)
            continue;
        check = 0;
        if(emp != -1)
        {
            for(int i = 0 ; i < m ; i++)
            {
                if(t[i] && t[i] != b[i])
                {
                    ops.push_back({i , emp});
                    apply_op(i , emp , t , b , ops);
                    check = 1;
                    break;
                }
            }
        }
    }
    for(int i = 0 ; i < m ; i++)
    {
        if(b[i] != t[i])
        {
            cout<<"-1\n";
            return 0;
        }
    }
    cout<<(int)ops.size()<<'\n';
    for(auto [u , v] : ops)
    {
        cout<<u + 1<<" "<<v + 1<<'\n';
    }
}

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