oj.uz

Submission #316470

# Submission time Handle Problem Language Result Execution time Memory
316470 2020-10-26T12:25:42 Z mohamedsobhi777 Sorting (IOI15_sorting) C++14
0 / 100
 1000 ms 896 KB 
#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] << " ";
        }
        exit(0);
}

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[i] = ans2[j].first;
                                Q[i] = ans2[j].second;
                        }
                        return ++i;
                }
        }

        assert(0);
        return 0;
}

Compilation message

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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 768 KB Output is correct
2 Correct 1 ms 768 KB Output is correct
3 Incorrect 1 ms 768 KB Unexpected end of file - int32 expected
4 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 768 KB Output is correct
2 Correct 1 ms 768 KB Output is correct
3 Incorrect 1 ms 768 KB Unexpected end of file - int32 expected
4 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 768 KB Output is correct
2 Incorrect 1 ms 800 KB Unexpected end of file - int32 expected
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 768 KB Output is correct
2 Correct 1 ms 768 KB Output is correct
3 Incorrect 1 ms 768 KB Unexpected end of file - int32 expected
4 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1089 ms 896 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 26.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1089 ms 896 KB Time limit exceeded
2 Halted 0 ms 0 KB -