제출 #259130

#제출 시각아이디문제언어결과실행 시간메모리
259130IOrtroiii정렬하기 (IOI15_sorting)C++14
0 / 100
1 ms384 KiB
// #include "sorting.h" #include <bits/stdc++.h> using namespace std; int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) { auto solve = [&](int mid) -> bool { vector<int> perm(N); for (int i = 0; i < N; ++i) { perm[i] = S[i]; } for (int i = 0; i < mid; ++i) swap(perm[X[i]], perm[Y[i]]); vector<int> invp(N); for (int i = 0; i < N; ++i) invp[perm[i]] = i; int ans = 0; for (int i = 0; i < N; ++i) { if (perm[i] == i) continue; int j = invp[perm[i]]; P[ans] = i; Q[ans++] = j; swap(perm[i], perm[j]); invp[perm[i]] = i; invp[perm[j]] = j; } for (int i = ans; i < mid; ++i) P[i] = Q[i] = 0; return ans <= mid; }; int low = 0, high = N; while (low < high) { int mid = (low + high) >> 1; if (solve(mid)) high = mid; else low = mid + 1; } solve(low); vector<int> perm(N); iota(perm.begin(), perm.end(), 0); vector<int> invp = perm; for (int i = low - 1; i >= 0; --i) { P[i] = invp[P[i]]; Q[i] = invp[Q[i]]; swap(perm[X[i]], perm[Y[i]]); invp[perm[X[i]]] = X[i]; invp[perm[Y[i]]] = Y[i]; } return low; }

컴파일 시 표준 에러 (stderr) 메시지

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:7:39: warning: unused parameter 'M' [-Wunused-parameter]
 int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
                                       ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...