Submission #434918

#	Time	Username	Problem	Language	Result	Execution time	Memory
434918		alextodoran	Sorting (IOI15_sorting)	C++17	100 / 100	245 ms	21060 KiB

sorting

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>
#include "sorting.h"

using namespace std;

typedef long long ll;

const int N_MAX = 200000;
const int M_MAX = 600000;

int findSwapPairs (int n, int p[], int m, int x[], int y[], int a[], int b[])
{
    function <int ()> minSwaps = [&] ()
    {
        int aux[n];
        int pos[n];
        for(int i = 0; i < n; i++)
        {
            aux[i] = p[i];
            pos[aux[i]] = i;
        }

        int swaps = 0;
        for(int i = 0; i < n; i++)
        {
            if(aux[i] != i)
            {
                int u = i, v = pos[i];
                swap(aux[u], aux[v]);
                swap(pos[aux[u]], pos[aux[v]]);
                swaps++;
            }
        }
        return swaps;
    };

    function <bool (int)> check = [&] (int swaps)
    {
        for(int i = 0; i < swaps; i++)
            swap(p[x[i]], p[y[i]]);

        bool answer = (minSwaps() <= swaps);

        for(int i = swaps - 1; i >= 0; i--)
            swap(p[x[i]], p[y[i]]);

        return answer;
    };

    int swaps;
    {
        int l = 0, r = m;
        while(l < r)
        {
            int mid = (l + r) / 2;
            if(check(mid) == true)
                r = mid;
            else
                l = mid + 1;
        }
        swaps = l;
    }

    {
        int aux[n];
        for(int i = 0; i < n; i++)
            aux[i] = p[i];
        for(int i = 0; i < swaps; i++)
            swap(aux[x[i]], aux[y[i]]);
        int pos[n];
        for(int i = 0; i < n; i++)
            pos[aux[i]] = i;
        int root[n];
        for(int i = 0; i < n; i++)
            root[p[i]] = i;

        int curr = 0;
        for(int i = 0; i < n; i++)
        {
            if(aux[i] != i)
            {
                swap(p[x[curr]], p[y[curr]]);
                swap(root[p[x[curr]]], root[p[y[curr]]]);

                int u = i, v = pos[i];
                swap(aux[u], aux[v]);
                swap(pos[aux[u]], pos[aux[v]]);
                a[curr] = root[aux[u]];
                b[curr] = root[aux[v]];

                swap(p[a[curr]], p[b[curr]]);
                swap(root[p[a[curr]]], root[p[b[curr]]]);

                curr++;
            }
        }
        while(curr < swaps)
        {
            a[curr] = 0;
            b[curr] = 0;
            curr++;
        }
    }
    return swaps;
}

• Subtask 1: 8 / 8
• Subtask 2: 12 / 12
• Subtask 3: 16 / 16
• Subtask 4: 18 / 18
• Subtask 5: 20 / 20
• Subtask 6: 26 / 26