| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1240169 | simplemind_31 | Sorting (IOI15_sorting) | C++20 | 0 ms | 0 KiB |
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]){
vector<int> a(N), inv_a(N);
// Apples b[p] = apple on plate p
vector<int> b(N);
for(int i=0;i<N;i++){
b[i]=S[i];
}
for(int i = 0; i < N; i++){
a[i] = i;
inv_a[i] = i;
}
// Function to check feasibility for t rounds
auto can = [&](int t){
// copy plates
vector<int> ca = a;
for(int i = 0; i < t; i++) swap(ca[X[i]], ca[Y[i]]);
// build pi: pi[i] = apple at slot i
vector<int> pi(N);
for(int i = 0; i < N; i++) pi[i] = b[ca[i]];
vector<bool> vis(N, false);
int cycles = 0;
for(int i = 0; i < N; i++){
if(!vis[i]){
cycles++;
int x = i;
while(!vis[x]){
vis[x] = true;
x = pi[x];
}
}
}
// swaps needed = N - cycles
return (N - cycles) <= t;
};
// binary search minimum t
int lo = 0, hi = M, mid, best = M;
while(lo <= hi){
mid = (lo + hi) / 2;
if(can(mid)){
best = mid;
hi = mid - 1;
} else lo = mid + 1;
}
// simulate adversary fully for best rounds
for(int i = 0; i < best; i++){
swap(a[X[i]], a[Y[i]]);
inv_a[a[X[i]]] = X[i];
inv_a[a[Y[i]]] = Y[i];
}
// build final pi
vector<int> pi(N);
for(int i = 0; i < N; i++) pi[i] = b[a[i]];
vector<bool> vis(N, false);
vector<pair<int,int>> ops;
// decompose into cycles and gather swaps
for(int i = 0; i < N; i++){
if(!vis[i]){
vector<int> cyc;
int x = i;
while(!vis[x]){
vis[x] = true;
cyc.push_back(x);
x = pi[x];
}
// break cycle of length l: swaps (cyc[0],cyc[j]) for j=1..l-1
for(size_t j = 1; j < cyc.size(); j++){
int u = cyc[0], v = cyc[j];
// swap apples on plates a[u], a[v]
ops.emplace_back(a[u], a[v]);
swap(b[a[u]], b[a[v]]);
}
}
}
// fill remaining with dummy swaps
while((int)ops.size() < best) ops.emplace_back(0, 0);
// output
for(int i=0;i<best;i++){
P[i]=ops[i].first;
Q[i]=ops[i].second;
}
return best;
/*cout << best << '\n';
for(int i = 0; i < best; i++){
cout << ops[i].first << " " << ops[i].second << "\n";
}*/
}