Submission #285156

#	Time	Username	Problem	Language	Result	Execution time	Memory
285156		SamAnd	Sorting (IOI15_sorting)	C++17	20 / 100	583 ms	9984 KiB

sorting

#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
const int N = 200005;

int n, m;
int a[N], b[N];

vector<int> g[N];

int c[N];
int k;

void dfs(int x)
{
    c[x] = k;
    for (int i = 0; i < g[x].size(); ++i)
    {
        int h = g[x][i];
        if (!c[h])
            dfs(h);
    }
}

vector<int> v[N];

int findSwapPairs(int N_, int S[], int M_, int X[], int Y[], int P[], int Q[])
{
    n = N_;
    m = M_;

    for (int i = 0; i < n; ++i)
        b[i] = S[i];

    for (int i = 0; i < n; ++i)
        a[i] = S[i];

    bool z = true;
    for (int i = 0; i < n - 1; ++i)
    {
        if (a[i] > a[i + 1])
        {
            z = false;
            break;
        }
    }

    if (z)
        return 0;

    for (int i = 0; i < m; ++i)
    {
        P[i] = Q[i] = 0;
        swap(a[X[i]], a[Y[i]]);

        for (int x = 0; x < n; ++x)
            g[x].clear();
        for (int j = i + 1; j < m; ++j)
        {
            g[X[j]].push_back(Y[j]);
            g[Y[j]].push_back(X[j]);
        }

        for (int x = 0; x < n; ++x)
            c[x] = 0;
        k = 0;
        for (int x = 0; x < n; ++x)
        {
            if (!c[x])
            {
                ++k;
                dfs(x);
            }
        }

        for (int i = 1; i <= k; ++i)
            v[i].clear();
        for (int x = 0; x < n; ++x)
            v[c[x]].push_back(a[x]);
        for (int i = 1; i <= k; ++i)
            sort(all(v[i]));
        for (int x = 0; x < n; ++x)
        {
            if (!binary_search(all(v[c[x]]), x))
            {
                vector<int> vv;
                for (int y = 0; y < n; ++y)
                {
                    if (c[y] == c[x])
                        vv.push_back(y);
                }
                int xx = -1;
                for (int i = 0; i < v[c[x]].size(); ++i)
                {
                    int u = v[c[x]][i];
                    if (!binary_search(all(vv), u))
                    {
                        for (int y = 0; y < n; ++y)
                        {
                            if (a[y] == u)
                            {
                                xx = y;
                                break;
                            }
                        }
                        break;
                    }
                }
                assert(xx != -1);
                for (int y = 0; y < n; ++y)
                {
                    if (a[y] == x)
                    {
                        swap(a[xx], a[y]);
                        P[i] = xx;
                        Q[i] = y;
                        break;
                    }
                }
                break;
            }
        }

         z = true;
        for (int i = 0; i < n - 1; ++i)
        {
            if (a[i] > a[i + 1])
            {
                z = false;
                break;
            }
        }
        if (z)
        {
            for (int j = 0; j <= i; ++j)
            {
                swap(b[X[j]], b[Y[j]]);
                swap(b[P[j]], b[Q[j]]);
            }
            for (int i = 0; i < n; ++i)
            {
                if (b[i] != i)
                {
                    assert(false);
                }
            }
            return (i + 1);
        }
    }
    assert(false);
    return -1;
}

Compilation message (stderr)

sorting.cpp: In function 'void dfs(int)':
sorting.cpp:22:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for (int i = 0; i < g[x].size(); ++i)
      |                     ~~^~~~~~~~~~~~~
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:81:18: warning: declaration of 'i' shadows a previous local [-Wshadow]
   81 |         for (int i = 1; i <= k; ++i)
      |                  ^
sorting.cpp:56:14: note: shadowed declaration is here
   56 |     for (int i = 0; i < m; ++i)
      |              ^
sorting.cpp:85:18: warning: declaration of 'i' shadows a previous local [-Wshadow]
   85 |         for (int i = 1; i <= k; ++i)
      |                  ^
sorting.cpp:56:14: note: shadowed declaration is here
   56 |     for (int i = 0; i < m; ++i)
      |              ^
sorting.cpp:98:26: warning: declaration of 'i' shadows a previous local [-Wshadow]
   98 |                 for (int i = 0; i < v[c[x]].size(); ++i)
      |                          ^
sorting.cpp:56:14: note: shadowed declaration is here
   56 |     for (int i = 0; i < m; ++i)
      |              ^
sorting.cpp:98:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |                 for (int i = 0; i < v[c[x]].size(); ++i)
      |                                 ~~^~~~~~~~~~~~~~~~
sorting.cpp:130:18: warning: declaration of 'i' shadows a previous local [-Wshadow]
  130 |         for (int i = 0; i < n - 1; ++i)
      |                  ^
sorting.cpp:56:14: note: shadowed declaration is here
   56 |     for (int i = 0; i < m; ++i)
      |              ^
sorting.cpp:145:22: warning: declaration of 'i' shadows a previous local [-Wshadow]
  145 |             for (int i = 0; i < n; ++i)
      |                      ^
sorting.cpp:56:14: note: shadowed declaration is here
   56 |     for (int i = 0; i < m; ++i)
      |              ^

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