# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
796439 | Josia | Sorting (IOI15_sorting) | C++17 | 140 ms | 27508 KiB |
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;
int countCycles(vector<int> p) {
vector<bool> vis(p.size());
int count=0;
for (int i = 0; i<(int)p.size(); i++) {
if (!vis[i]) count++;
int pos = i;
while(!vis[pos]) {
vis[pos] = 1;
pos = p[pos];
}
}
return count;
}
vector<int> doSwaps(vector<int> input, vector<pair<int, int>> swaps, int number) {
for (int i = 0; i<number; i++) {
swap(input[swaps[i].first], input[swaps[i].second]);
}
return input;
}
int findSwapPairs(int N, int _S[], int M, int X[], int Y[], int P[], int Q[]) {
vector<int> S(N);
for (int i = 0; i<N; i++) S[i] = _S[i];
vector<pair<int, int>> swapsOther;
for (int i = 0; i<M; i++) swapsOther.push_back({X[i], Y[i]});
int l = 0, r = M;
while (l < r) {
int m = (l+r)/2;
int cycles = countCycles(doSwaps(S, swapsOther, m));
// cerr << m << " " << cycles << "\n";
if (N-cycles <= m) {
r = m;
} else {
l = m+1;
}
}
vector<int> hisPerm = doSwaps(S, swapsOther, l);
// cerr << l << "\n";
// for (int i: hisPerm) cerr << i << " ";
// cerr << "\n";
vector<pair<int, int>> mySwapsValues;
vector<int> hisPermInv(N);
for (int i = 0; i<N; i++) {
hisPermInv[hisPerm[i]] = i;
}
for (int i = 0; i<N; i++) {
if (hisPerm[i] == i) continue;
mySwapsValues.push_back({i, hisPerm[i]});
int miau = hisPerm[i];
swap(hisPerm[hisPermInv[i]], hisPerm[i]);
swap(hisPermInv[i], hisPermInv[miau]);
}
// for (int i: hisPerm) cerr << i << " ";
// cerr << "\n";
assert(is_sorted(hisPerm.begin(), hisPerm.end()));
// for (auto i: mySwapsValues) {cerr << i.first << " " << i.second << "\n";}
vector<int> SInv(N);
for (int i = 0; i<N; i++) SInv[S[i]] = i;
for (int i = 0; i<mySwapsValues.size(); i++) {
swap(SInv[S[swapsOther[i].first]], SInv[S[swapsOther[i].second]]);
swap(S[swapsOther[i].first], S[swapsOther[i].second]);
P[i] = SInv[mySwapsValues[i].first];
Q[i] = SInv[mySwapsValues[i].second];
assert(S[P[i]] == mySwapsValues[i].first);
assert(S[Q[i]] == mySwapsValues[i].second);
swap(SInv[S[P[i]]], SInv[S[Q[i]]]);
swap(S[P[i]], S[Q[i]]);
}
assert(is_sorted(mySwapsValues.begin(), mySwapsValues.end()));
assert(mySwapsValues.size() == l || mySwapsValues.size()+1 == l);
if (mySwapsValues.size() < l) {
P[l-1]=0;
Q[l-1]=0;
}
return l;
}
Compilation message (stderr)
# | 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... |