Submission #316542

#	Time	Username	Problem	Language	Result	Execution time	Memory
316542		mohamedsobhi777	Sorting (IOI15_sorting)	C++14	74 / 100	1096 ms	8696 KiB

sorting

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

using namespace std;
const int _N = 2e5;

int n;
int s[_N], _s[_N];
int x[_N], y[_N];
int nxt[_N];
int t;
int viz[_N];
int Nxt[_N];
int cyc = 0;
int pos[_N];
int rep[_N];

int cycles()
{
        ++t;
        int ret = 0;
        for (int i = 0; i < n; ++i)
        {
                int cnt = 1;
                int cur = Nxt[i];
                if (viz[i] == t)
                        continue;
                ++ret;
                while (cur != i)
                {
                        viz[cur] = t;
                        cur = Nxt[cur];
                        ++cnt;
                }
                viz[cur] = t;
        }
        return ret;
}
vector<pair<int, int>> ans, ans2;

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

        for (int i = 0; i < n; ++i)
        {
      //          cout << rep[i] << " ";
        }
    //    cout << "\n";
        for (int i = 0; i < X; ++i)
        {
       //         cout << rep[x[i]] << " " << rep[y[i]] << "()\n";
                swap(pos[x[i]], pos[y[i]]);
                int x1 = 0, x2 = 0;
               // cout << _s[x[i]] << " " << _s[y[i]] << "!!\n";
                for (int j = 0; j < n; ++j)
                {
                        if (s[j] == _s[x[i]])
                        {
                                x1 = j;
                        }
                        if (s[j] == _s[y[i]])
                        {
                                x2 = j;
                        }
                }
                //cout << x1 << " " << x2 << "@@\n";
                swap(rep[x1], rep[x2]);
                for (int j = 0; j < n; ++j)
                {
                  //      cout << rep[j] << " ";
                }
                //cout << "---\n";
                ans2[i] = {rep[ans[i].first], rep[ans[i].second]};
                swap(_s[x[i]], _s[y[i]]);
                //swap(pos[x[i]], pos[y[i]]);
        }
        for (int i = 0; i < X; ++i)
        {
                break;
                /*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]]);*/
        }
        return;
        for (int i = 0; i < X; ++i)
        {
                swap(_s[x[i]], _s[y[i]]);
                swap(_s[ans2[i].first], _s[ans2[i].second]);
        }
}

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)
        {
                Nxt[i] = S[i];
                s[i] = S[i];
                _s[i] = S[i];
                //pos[i] = i;
                rep[i] = i;
        }
        cyc = cycles();

        if (n - cycles() == 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]]);
                swap(rep[X[i]], rep[Y[i]]);
                //swap(pos[X[i]], pos[Y[i]]);
                swap(Nxt[X[i]], Nxt[Y[i]]);
                if (X[i] != Y[i])
                {
                        if (Nxt[X[i]] == X[i] || Nxt[Y[i]] == Y[i])
                        {
                                ++cyc;
                        }
                        else
                        {
                                --cyc;
                        }
                }
                if (n - cycles() <= i + 1)
                {
                        solve(i + 1);
                        for (int j = 0; j <= i; ++j)
                        {
                                P[j] = ans2[j].first;
                                Q[j] = ans2[j].second;
                        }
                        return ++i;
                }
        }
        return 0;
}

Compilation message (stderr)

sorting.cpp: In function 'void solve(int)':
sorting.cpp:57: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]
   57 |         while (ans.size() < X)
      |                ~~~~~~~~~~~^~~

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