This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
bool trySwapPairs(int n, int S[], int m, int X[], int Y[], int P[], int Q[]) {
vector<int> targetArr(n);
vector<int> revInd(n);
int countMatches = 0;
for(int i = 0; i < n; i++) {
targetArr[i] = i;
if(S[i] == i) countMatches++;
}
for(int i = m-1; i >= 0; i--) {
swap(targetArr[X[i]], targetArr[Y[i]]);
}
for(int i = 0; i < n; i++) {
revInd[targetArr[i]] = i;
}
vector<int> notGood(n);
for(int i = 0; i < n; i++) {
if(S[i] != targetArr[i]) {
notGood[i] = true;
}
}
vector<int> nums(n);
vector<int> otherRevInd(n);
auto swapTwo = [&](int i, int a, int b) {
if(a == S[a]) countMatches--;
if(b == S[b]) countMatches--;
swap(nums[otherRevInd[a]], nums[otherRevInd[b]]);
swap(otherRevInd[a], otherRevInd[b]);
swap(S[a], S[b]);
P[i] = a; Q[i] = b;
if(a == S[a]) countMatches++;
if(b == S[b]) countMatches++;
};
vector<int> taken(n, false);
vector<pair<int, int>> pairs;
pairs.clear();
for(int i = 0; i < n; i++) {
taken[i] = false;
}
vector<int> v;
for(int i = 0; i < n; i++) {
otherRevInd[i] = i;
nums[i] = i;
if(taken[i]) continue;
taken[i] = true;
v.push_back(i);
int x = revInd[S[i]];
while(x != i) {
taken[x] = true;
v.push_back(x);
x = revInd[S[x]];
}
for(int j = 1; j < v.size(); j++) {
pairs.push_back({v[j-1], v[j]});
}
v.clear();
}
while(pairs.size() < m) pairs.push_back({0, 0});
for(int i = 0; i < m; i++) {
if(countMatches == n) {
m = i;
break;
}
if(X[i] != Y[i]) {
if(X[i] == S[X[i]]) countMatches--;
if(Y[i] == S[Y[i]]) countMatches--;
swap(nums[otherRevInd[X[i]]], nums[otherRevInd[Y[i]]]);
swap(otherRevInd[X[i]], otherRevInd[Y[i]]);
swap(S[X[i]], S[Y[i]]);
if(X[i] == S[X[i]]) countMatches++;
if(Y[i] == S[Y[i]]) countMatches++;
}
swapTwo(i, nums[pairs[i].first], nums[pairs[i].second]);
/*
cout << "Current state: ";
for(int j = 0; j < n; j++) cout << S[j] << ' ';
cout << '\n';
*/
}
return (countMatches == n);
}
int findSwapPairs(int n, int R[], int m, int X[], int Y[], int P[], int Q[]) {
int V[200001];
int l = -1, r = min(m, n+1);
while(l != r - 1) {
for(int i = 0; i < n; i++) {
V[i] = R[i];
}
int mid = (l + r + 1) / 2;
if(trySwapPairs(n, V, mid, X, Y, P, Q)) r = mid;
else l = mid;
}
trySwapPairs(n, R, r, X, Y, P, Q);
return r;
}
Compilation message (stderr)
sorting.cpp: In function 'bool trySwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:57:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
57 | for(int j = 1; j < v.size(); j++) {
| ~~^~~~~~~~~~
sorting.cpp:62:24: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
62 | while(pairs.size() < m) pairs.push_back({0, 0});
| ~~~~~~~~~~~~~^~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |