Submission #712186

#	Time	Username	Problem	Language	Result	Execution time	Memory
712186		neki	Sorting (IOI15_sorting)	C++14	100 / 100	501 ms	23412 KiB

sorting

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

using namespace std;

int findSwapPairs(int n, int s[], int m, int x[], int y[], int a[], int b[])
{
    int is[n];
    for (int i = 0; i < n; ++i)
        is[s[i]] = i;

    function<bool(int)> solve = [&](int meja)
    {
        int p[n], ip[n], z[n], iz[n];
        for (int i = 0; i < n; ++i)
            p[i] = i, z[i] = iz[i] = i;
        for (int i = meja - 1; i >= 0; --i)
            swap(p[x[i]], p[y[i]]);
        for (int i = 0; i < n; ++i)
            ip[p[i]] = i;

        int j = 0;
        for (int i = meja - 1; i >= 0; --i)
        {
            /*for (int t = 0; t < n; ++t)
                cout << z[t] << " ";
            cout << endl;*/
            while (j < n && j == s[ip[iz[j]]])
                ++j;
            if (j < n)
                a[i] = iz[j], b[i] = p[is[j]];
            else
                a[i] = b[i] = 0;

            swap(iz[z[a[i]]], iz[z[b[i]]]);
            swap(z[a[i]], z[b[i]]);

            /*cout << "prej" << endl;
            for (int t = 0; t < n; ++t)
                cout << s[ip[iz[t]]] << " ";
            cout << endl;*/

            swap(iz[z[x[i]]], iz[z[y[i]]]);
            swap(z[x[i]], z[y[i]]);

            swap(p[ip[x[i]]], p[ip[y[i]]]);
            swap(ip[x[i]], ip[y[i]]);

            /*cout << "po" << endl;
            for (int t = 0; t < n; ++t)
                cout << s[ip[iz[t]]] << " ";
            cout << endl;*/
        }
        while (j < n && j == s[ip[iz[j]]])
            ++j;
        return j == n;
    };

    int l = 0, r = m;
    while (l < r)
    {
        int mid = (l + r) / 2;

        if (solve(mid))
            r = mid;
        else
            l = mid + 1;
    }
    solve(l);
    // solve(l);

    return l;
}

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