# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
425958 | 2021-06-13T12:35:01 Z | _fractal | 정렬하기 (IOI15_sorting) | C++14 | 0 ms | 0 KB |
#include "sorting.h" #include <iostream> #include <algorithm> using namespace std; int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) { int A[N], pos[N]; for (int i = 0; i < N; ++i) A[i] = i; for (int i = M - 1; i >= 1; --i) swap(A[X[i]], A[Y[i]]);/* for (int i = 0; i < M; ++i) cerr << P[i] << " " << Q[i] << '\n'; cerr << "---------\n";*/ swap(S[X[0]], S[Y[0]]); int r = 0; for (int i = 0; i < M; ++i) { for (int j = 0; j < N; ++j) pos[A[j]] = j; for (int j = 0; j < N; ++j) { if (pos[S[j]] != j) { Q[i] = j, P[i] = pos[S[j]]; ++r; break; } } if (Q[i]] == P[i]) break; swap(S[Q[i]], S[P[i]]); if (i + 1 < M) { swap(S[X[i + 1]], S[Y[i + 1]]); swap(A[X[i + 1]], A[Y[i + 1]]); } }/* for (int i = 0; i < M; ++i) { cerr << X[i] << " " << Y[i] << '\n'; if (i < r) cerr << P[i] << " " << Q[i] << '\n'; } for (int i = 0; i < N; ++i) cerr << S[i] << " \n"[i + 1 == N];*/ return r; }