| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 622422 | 2022-08-04T09:21:07 Z | 8e7 | Sorting (IOI15_sorting) | C++17 | 0 ms | 0 KB |
//Challenge: Accepted
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r){
while (l != r) cout << *l << " ", l++;
cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 200005
#define mod 1000000007
#define pii pair<int, int>
#define ff first
#define ss second
#include "sorting.h"
int findSwapPairs(int n, int S[], int M, int X[], int Y[], int P[], int Q[]) {
//int low = -1, up = M;
vector<int> pos(n), rev(n);
auto getp = [&] (int k) {
vector<int> ret(n);
vector<int> a(n);
for (int i = 0;i < n;i++) a[i] = i;
//[0, mid)
for (int i = k-1;i >= 0;i--) {
swap(a[X[i]], a[Y[i]]);
}
for (int i = 0;i < n;i++) {
pos[a[i]] = i;
rev[i] = a[i];
ret[a[i]] = S[i];
}
return ret;
};
while (low < up - 1) {
int mid = (low + up) / 2;
vector<int> v = getp(mid);
vector<bool> vis(n, 0);
int num = n;
for (int i = 0;i < n;i++) {
if (vis[i]) continue;
int cur = i;
do {
vis[cur] = 1;
cur = v[cur];
} while (!vis[cur]);
num--;
}
if (num <= mid) up = mid;
else low = mid;
}
vector<int> v = getp(up);
vector<bool> vis(n, 0);
vector<pii> sw;
for (int i = 0;i < n;i++) {
if (vis[i]) continue;
int cur = i;
do {
vis[cur] = 1;
if (!vis[v[cur]]) sw.push_back({cur, v[cur]});
cur = v[cur];
} while (!vis[cur]);
}
reverse(sw.begin(), sw.end());
for (int i = 0;i < up;i++) {
int vx = rev[X[i]], vy = rev[Y[i]];
swap(rev[X[i]], rev[Y[i]]);
swap(pos[vx], pos[vy]);
if (i < sw.size()) {
P[i] = pos[sw[i].ff];
Q[i] = pos[sw[i].ss];
} else {
P[i] = Q[i] = 0;
}
}
return up;
}