| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 917115 | 2024-01-27T08:43:50 Z | azosi | 정렬하기 (IOI15_sorting) | C++17 | 0 ms | 0 KB |
#include <bits/stdc++.h>
using namespace std;
int A[200001];
int B[200001], chk[200001];
pair<int, int> qry[600003];
int n, m;
bool f(int k) {
for (int i = 0; i < n; ++i) B[i] = A[i];
memset(chk, 0, sizeof(chk));
for (int i = 0; i < k; ++i) swap(B[qry[i].first], B[qry[i].second]);
int ret = 0;
for (int i = 0; i < n; ++i) {
if (!chk[i]) {
int cnt = 1;
chk[i] = 1;
int here = i;
while (!chk[B[here]]) {
here = B[here];
chk[here] = 1;
cnt++;
}
ret += cnt - 1;
}
}
return ret <= k;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n;
for (int i = 0; i < n; ++i) cin >> A[i];
cin >> m;
for (int i = 0; i < m; ++i) cin >> qry[i].first >> qry[i].second;
int l = 0, r = m;
int round = -1;
while (l <= r) {
int mid = l + r >> 1;
if (f(mid)) {
round = mid;
r = mid - 1;
} else l = mid + 1;
}
cout << round << '\n';
memset(chk, 0, sizeof(chk));
for (int i = 0; i < round; ++i) {
swap(A[qry[i].first], A[qry[i].second]);
}
vector<pair<int, int>> ans;
for (int i = 0; i < n; ++i) {
if (!chk[i]) {
chk[i] = 1;
vector<int> cycle;
int here = i;
cycle.push_back(here);
while (!chk[A[here]]) {
here = A[here];
cycle.push_back(here);
chk[here] = 1;
}
if (cycle.size() >= 2) {
for (int j = 1; j < cycle.size(); ++j) {
ans.push_back({cycle[0], cycle[j]});
swap(A[cycle[0]], A[cycle[j]]);
}
}
}
}
for (auto [a, b]: ans) {
cout << a << " " << b << '\n';
}
if (round > ans.size()) {
cout << 0 << " " << 0 << '\n';
}
for (int i = 0; i < n; ++i) {
assert(A[i] == i);
}
}