Submission #316475

#	Time	Username	Problem	Language	Result	Execution time	Memory
316475		mohamedsobhi777	Sorting (IOI15_sorting)	C++14	0 / 100	1084 ms	896 KiB

sorting

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

using namespace std;
const int _N = 1e5;

int n;
int s[_N], _s[_N];
int x[_N], y[_N];
int nxt[_N];

int check()
{
        int ret = 0;
        memset(nxt, -1, sizeof nxt);
        for (int i = 0; i < n; ++i)
        {
                nxt[i] = s[i];
        }
        for (int i = 0; i < n; ++i)
        {
                int cnt = 1;
                int cur = nxt[i];
                while (cur != i)
                {
                        cur = nxt[cur];
                        ++cnt;
                }
                ret += --cnt;
        }
        return ret;
}
vector<pair<int, int>> ans, ans2;

void solve(int X)
{

        memset(nxt, -1, sizeof nxt);
        for (int i = 0; i < n; ++i)
        {
                nxt[i] = s[i];
        }

        map<int, int> vis;
        for (int i = 0; i < n; ++i)
        {
                if (vis[i])
                        continue;
                int cur = i;
                while (nxt[cur] != i)
                {
                        ++vis[cur];
                        ans.push_back({cur, nxt[cur]});
                        swap(s[cur], s[nxt[cur]]);
                        cur = nxt[cur];
                }
                ++vis[cur];
        }
        while (ans.size() < X)
        {
                ans.push_back({0, 0});
        }
        ans2.resize(X);

        for (int i = 0; i < X; ++i)
        {
                int rep[n + 1];
                for (int j = 0; j < n; ++j)
                        rep[j] = j;
                for (int j = i + 1; j < X; ++j)
                {
                        swap(rep[x[j]], rep[y[j]]);
                }
                ans2[i] = {rep[ans[i].first], rep[ans[i].second]};
                swap(rep[x[i]], rep[y[i]]);
        }
        for (int i = 0; i < X; ++i)
        {
                swap(_s[x[i]], _s[y[i]]);
                swap(_s[ans2[i].first], _s[ans2[i].second]);
        }
        for (int i = 0; i < n; ++i)
        {
                //cout << _s[i] << " ";
        }
}

void print()
{
        for (int i = 0; i < n; ++i)
        {
                cout << s[i] << " ";
        }
        cout << "-----------\n";
}

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[])
{
        n = N;
        for (int i = 0; i < N; ++i)
        {
                s[i] = S[i];
                _s[i] = S[i];
        }
        if (check() == 0)
        {
                return 0;
        }

        for (int i = 0; i < M; ++i)
        {
                x[i] = X[i];
                y[i] = Y[i];
                swap(s[X[i]], s[Y[i]]);
                if (check() <= i + 1)
                {
                        solve(i + 1);
                        for (int j = 0; j <= i; ++j)
                        {
                                P[j] = ans2[j].first;
                                Q[j] = ans2[j].second;
                        }
                        return ++i;
                }
        }

        //assert(0);
        return 0;
}

Compilation message (stderr)

sorting.cpp: In function 'void solve(int)':
sorting.cpp:59:27: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   59 |         while (ans.size() < X)
      |                ~~~~~~~~~~~^~~

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