제출 #316546

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
316546		mohamedsobhi777	정렬하기 (IOI15_sorting)	C++14	0 / 100	2 ms	640 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)
                pos[s[i]] = i;

        for (int i = 0; i < X; ++i)
        {
                int x1 = pos[_s[x[i]]];
                int x2 = pos[_s[y[i]]];
                swap(rep[x1], rep[x2]);
                ans2[i] = {rep[ans[i].first], rep[ans[i].second]};
                swap(_s[x[i]], _s[y[i]]);
        }
}

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];
                rep[i] = i;
        }
        cyc = cycles();

        if (n - cyc == 0)
                return 0;
        int k = n - cyc;
        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(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 (!k--)
                {
                        cyc = cycles();
                        if (n - cyc <= i + 1)
                        {
                                solve(i + 1);
                                for (int j = 0; j <= i; ++j)
                                {
                                        P[j] = ans2[j].first;
                                        Q[j] = ans2[j].second;
                                }
                                return ++i;
                        }
                        k = max(0, n - cyc - i - 1);
                }
        }
        return 0;
}

컴파일 시 표준 에러 (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: 0 / 8
• Subtask 2: 0 / 12
• Subtask 3: 0 / 16
• Subtask 4: 0 / 18
• Subtask 5: 0 / 20
• Subtask 6: 0 / 26