Submission #739983

#	Time	Username	Problem	Language	Result	Execution time	Memory
739983		danikoynov	Parking (CEOI22_parking)	C++14	60 / 100	337 ms	106824 KiB

Main

/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const int maxn = 2e5 + 10;
int n, m, t[maxn][2], sz[maxn];
set < int > pos[maxn];
vector < int > g[2 * maxn];
vector < pair < int, int > > ans;
int used[maxn];
vector < int > path;
void dfs(int v)
{
    used[v] = 1;
    path.push_back(v);
    for (int u : g[v])
    {
        if (used[u])
            continue;
        dfs(u);
    }
}


void move_at(int i, int j)
{
    t[j][sz[j]] = t[i][sz[i] - 1];
    t[i][sz[i] - 1] = 0;
    sz[i] --;
    sz[j] ++;
    ans.push_back({i, j});
}

void solve_chain(vector < int > ch)
{

    deque < int > dq;
    for (int v : ch)
        dq.push_back(v);

    while(!dq.empty())
    {
        if (dq.size() == 2)
        {
            move_at(dq[0], dq[1]);
            dq.pop_front();
            dq.pop_front();
            break;
        }
        if (dq[1] > m)
        {
            move_at(dq[1] - m, dq[0]);
            dq.pop_front();
            dq.pop_front();
        }
        else
        {
            move_at(dq[dq.size() - 2] - m, dq.back());
            dq.pop_back();
            dq.pop_back();
        }
        /**for (int i =0 ; i < dq.size(); i ++)
            cout << dq[i] << " ";
        cout << endl;*/

    }
    /**if (ch[1] <= m)
        reverse(ch.begin(), ch.end());
        for (int i = 0; i < ch.size(); i ++)
            cout << ch[i] << " ";
        cout << endl;
    for (int i = 1; i < ch.size(); i += 2)
    {
        int p1 = ch[i - 1], p2 = ch[i], j = 0;
        if (p2 > m)
        {
            p2 -= m;
            j = 1;
        }

        t[p1][1] = t[p2][j];
        t[p2][j] = 0;
        ans.push_back({p2, p1});
        sz[p2] --;
        sz[p1] ++;

    }*/
}

void solve()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i ++)
    {
        cin >> t[i][0] >> t[i][1];
    }

    for (int i = 1; i <= m; i ++)
    {
        if (t[i][0] == t[i][1] && t[i][0] != 0)
            continue;

        if (t[i][0] != 0)
            sz[i] ++;
        if (t[i][1] != 0)
            sz[i] ++;
        for (int j = 0; j < sz[i]; j ++)
        {
            pos[t[i][j]].insert(j * m + i);
        }

        if (sz[i] == 2)
        {
            g[i].push_back(m + i);
            g[m + i].push_back(i);
        }
    }

    for (int i = 1; i <= n; i ++)
    {
        int l = *pos[i].begin();
        pos[i].erase(l);
        int r = *pos[i].begin();
        pos[i].erase(r);
        g[l].push_back(r);
        g[r].push_back(l);
    }


    deque < vector < int > > chn, cyc;

    for (int i = 1; i <= 2 * m; i ++)
    {
        if (!used[i] && g[i].size() == 1)
        {
            path.clear();
            dfs(i);
            int up = -1;
            for (int i = 1; i < path.size(); i ++)
            {
                if (path[i] > m && path[i - 1] > m)
                {
                    up = i - 1;
                    break;
                }
            }
            if (up == -1)
                chn.push_front(path);
            else
                chn.push_back(path);
        }
    }

    for (int i = 1; i <= 2 * m; i ++)
    {
        if (!used[i] && g[i].size() > 0)
        {
            path.clear();
            dfs(i);
            cyc.push_back(path);
        }
    }

    while(true)
    {
        if (!chn.empty())
        {
            path = chn.front();
            /// cout << path.size() << endl;
            chn.pop_front();
            int up = -1;
            for (int i = 1; i < path.size(); i ++)
            {
                if (path[i] > m && path[i - 1] > m)
                {
                    up = i - 1;
                    break;
                }
            }

            if (up == -1)
            {
                solve_chain(path);
            }
            else
            {
                int cur = 1;
                while(cur <= m && t[cur][0] != 0)
                    cur ++;
                if (cur > m)
                {
                    cout << -1 << endl;
                    exit(0);
                }
                move_at(path[up] - m, cur);
                move_at(path[up + 1] - m, cur);
                /**t[cur][0] = t[cur][1] = t[path[up] - m][1];
                t[path[up] - m][1] = 0;
                t[path[up + 1] - m][1] = 0;
                sz[path[up] - m] --;
                sz[path[up + 1] - m] --;
                sz[cur] = 2;
                ans.push_back({path[up] - m, cur});
                ans.push_back({path[up + 1] - m, cur});*/

                vector < int > left, right;
                for (int i = 0; i < up; i ++)
                    left.push_back(path[i]);
                for (int i = up + 2; i < path.size(); i ++)
                    right.push_back(path[i]);
                chn.push_front(left);
                chn.push_back(right);
            }
        }
        else if (!cyc.empty())
        {
            path = cyc.front();
            cyc.pop_front();
            vector < int > db;
            for (int i = 1; i < path.size(); i ++)
            {
                if (path[i] > m && path[i - 1] > m)
                {
                    db.push_back(i - 1);
                    break;
                }
            }

            if (db.size() == 0)
            {
                int idx = 0;
                while(true)
                {
                    int row1 = path[idx];
                    int row2 = path[idx + 1];
                    if (row1 > m)
                        row1 -= m;
                    if (row2 > m)
                        row2 -= m;
                    if (row1 == row2)
                        idx ++;
                    else
                    {
                        break;
                    }
                }

                int cur = 1;
                while(cur <= m && t[cur][0] != 0)
                    cur ++;
                if (cur > m)
                {
                    cout << -1 << endl;
                    exit(0);
                }
                vector < int > new_chain;
                if (path[idx] > m)
                {
                    //cout << path[idx] << " : " << path[idx + 1] << endl;
                    move_at(path[idx] - m, cur);
                    new_chain.push_back(cur);
                    for (int i = idx + 1; i < path.size(); i ++)
                        new_chain.push_back(path[i]);
                    for (int i = 0; i < idx; i ++)
                        new_chain.push_back(path[i]);
                    /** for (int i = 0; i < new_chain.size(); i ++)
                         cout << new_chain[i] << " ";
                     cout << endl;*/
                }
                else
                {
                    move_at(path[idx + 1] - m, cur);
                    new_chain.push_back(cur);
                    for (int i = idx; i >= 0; i --)
                        new_chain.push_back(path[i]);
                    for (int i = (int)(path.size()) - 1; i > idx + 1; i --)
                        new_chain.push_back(path[i]);
                }
                chn.push_front(new_chain);

            }
            else if (db.size() > 0)
            {
                ///cout << "here" << endl;
                int cur = 1;
                while(cur <= m && t[cur][0] != 0)
                    cur ++;
                if (cur > m)
                {
                    cout << -1 << endl;
                    exit(0);
                }
                int up = db[0];
                move_at(path[up] - m, cur);
                move_at(path[up + 1] - m, cur);
                /**t[cur][0] = t[cur][1] = t[path[up] - m][1];
                t[path[up] - m][1] = 0;
                t[path[up + 1] - m][1] = 0;
                sz[path[up] - m] --;
                sz[path[up + 1] - m] --;
                sz[cur] = 2;
                ans.push_back({path[up] - m, cur});
                ans.push_back({path[up + 1] - m, cur});*/


                vector < int > new_chain;
                for (int i = up - 1; i >= 0; i --)
                    new_chain.push_back(path[i]);
                for (int i = (int)(path.size()) - 1; i > up + 1; i --)
                    new_chain.push_back(path[i]);
                chn.push_back(new_chain);

            }
            /**else
            {
                int
            }*/
            ///cout << "Here" << endl;
        }
        else
        {
            break;
        }
    }

    cout << ans.size() << endl;
    for (pair < int, int > cur : ans)
    {
        cout << cur.first << " " << cur.second << endl;
    }
}

int main()
{
    solve();
    return 0;
}
/**
3 5
1 2
3 2
1 3
0 0

3 4
3 0
1 3
2 0
1 2


*/

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:156:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  156 |             for (int i = 1; i < path.size(); i ++)
      |                             ~~^~~~~~~~~~~~~
Main.cpp:189:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  189 |             for (int i = 1; i < path.size(); i ++)
      |                             ~~^~~~~~~~~~~~~
Main.cpp:226:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  226 |                 for (int i = up + 2; i < path.size(); i ++)
      |                                      ~~^~~~~~~~~~~~~
Main.cpp:237:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  237 |             for (int i = 1; i < path.size(); i ++)
      |                             ~~^~~~~~~~~~~~~
Main.cpp:279:45: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  279 |                     for (int i = idx + 1; i < path.size(); i ++)
      |                                           ~~^~~~~~~~~~~~~

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