Submission #801990

#	Time	Username	Problem	Language	Result	Execution time	Memory
801990		caganyanmaz	Sorting (IOI15_sorting)	C++17	100 / 100	146 ms	21080 KiB

sorting

#include "sorting.h"
#define pb push_back
#include <bits/stdc++.h>
using namespace std;

constexpr static int MXSIZE = 2e5;
int e[MXSIZE];
int n;
int component[MXSIZE];
int *s, *x, *y;

void dfs(int node, int c)
{
        component[node] = c;
        if (component[e[node]] == -1)
                dfs(e[node], c);
}

void construct(int k)
{
        for (int i = 0; i < n; i++)
                e[i] = s[i];
        for (int i = 0; i < k; i++)
                swap(e[x[i]], e[y[i]]);
}

bool is_possible(int k)
{
        construct(k);
        for (int i = 0; i < n; i++)
                component[i] = -1;
        int last = 0;
        for (int i = 0; i < n; i++)
                if (component[i] == -1)
                        dfs(i, last++);
        return (n-last) <= k;
}

int rs[MXSIZE];

int findSwapPairs(int nn, int ss[], int _m, int xx[], int yy[], int p[], int q[])
{
        n = nn;
        s = ss, x = xx, y = yy;
        int l = -1, r = _m+1;
        while (r - l > 1)
        {
                int m = l+r>>1;
                if (is_possible(m))
                        r = m;
                else
                        l = m;
        }
        construct(r);
        vector<array<int, 2>> swaps;
        for (int i = 0; i < n; i++)
        {
                while (e[i] != i)
                {
                        swaps.pb({e[i], e[e[i]]});
                        swap(e[i], e[e[i]]);
                }
        }
        assert(swaps.size() <= r);
        for (int i = 0; i < n; i++)
        {
                rs[s[i]] = i;
                e[i] = s[i];
        }
        for (int i = 0; i < r; i++)
        {
                swap(e[x[i]], e[y[i]]);
                rs[e[x[i]]] = x[i];
                rs[e[y[i]]] = y[i];
                if (i < swaps.size())
                {
                        p[i] = rs[swaps[i][0]];
                        q[i] = rs[swaps[i][1]];
                        swap(e[p[i]], e[q[i]]);
                        rs[e[p[i]]] = p[i];
                        rs[e[q[i]]] = q[i];
                }
                else
                {
                        p[i] = 0;
                        q[i] = 0;
                }
        }
        return r;
}

Compilation message (stderr)

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:48:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   48 |                 int m = l+r>>1;
      |                         ~^~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from sorting.cpp:3:
sorting.cpp:64:29: warning: comparison of integer expressions of different signedness: 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   64 |         assert(swaps.size() <= r);
      |                ~~~~~~~~~~~~~^~~~
sorting.cpp:75:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |                 if (i < swaps.size())
      |                     ~~^~~~~~~~~~~~~~

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