#include <bits/stdc++.h>
using namespace std;
#define starburst ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long
#define pii pair<int,int>
#define pb push_back
int findSwapPairs(int N, int *S, int M, int *X, int *Y, int *P, int *Q){
int lb = 0, rb = M;
while(lb != rb){
int mid = (lb + rb) / 2;
vector<int> cur(N), end(N), curid(N), endid(N);
for(int i = 0; i < N; ++i) cur[i] = end[i] = S[i], curid[S[i]] = endid[S[i]] = i;
for(int i = 0; i < mid; ++i){
int x = X[i], y = Y[i];
endid[end[x]] = y, endid[end[y]] = x;
swap(end[x], end[y]);
}
int j = N - 1;
for(int i = mid - 1; i >= 0; --i){
while(j >= 0 && end[j] == j) j--;
if(j < 0) break;
int id = mid - i - 1;
int x = X[id], y = Y[id];
swap(curid[cur[x]], curid[cur[y]]);
swap(cur[x], cur[y]);
int a = end[j], b = j;
swap(curid[a], curid[b]);
swap(endid[a], endid[b]);
swap(cur[curid[a]], cur[curid[b]]);
swap(end[endid[a]], end[endid[b]]);
}
while(j >= 0 && end[j] == j) j--;
if(j < 0) rb = mid;
else lb = mid + 1;
}
vector<int> cur(N), end(N), curid(N), endid(N);
for(int i = 0; i < N; ++i) cur[i] = end[i] = S[i], curid[S[i]] = endid[S[i]] = i;
for(int i = 0; i < lb; ++i){
int x = X[i], y = Y[i];
endid[end[x]] = y, endid[end[y]] = x;
swap(end[x], end[y]);
}
int j = N - 1;
for(int i = lb - 1; i >= 0; --i){
while(j >= 0 && end[j] == j) j--;
if(j < 0) break;
int id = lb - i - 1;
int x = X[id], y = Y[id];
swap(curid[cur[x]], curid[cur[y]]);
swap(cur[x], cur[y]);
for(auto x:cur) cout << x << ' ';
cout << '\n';
int a = end[j], b = j;
P[id] = curid[a], Q[id] = curid[b];
if(P[id] > Q[id]) swap(P[id], Q[id]);
swap(curid[a], curid[b]);
swap(endid[a], endid[b]);
swap(cur[curid[a]], cur[curid[b]]);
swap(end[endid[a]], end[endid[b]]);
for(auto x:cur) cout << x << ' ';
cout << '\n';
}
return lb;
}
/*void solve(){
int n; cin >> n;
int S[n];
for(int i = 0; i < n; ++i) cin >> S[i];
int m; cin >> m;
int X[m], Y[m], P[m], Q[m];
fill(P, P + m + 1, 0);
fill(Q, Q + m + 1, 0);
for(int i = 0; i < m; ++i) cin >> X[i] >> Y[i];
int R = findSwapPairs(n, S, m, X, Y, P, Q);
cout << R << '\n';
for(int i = 0; i < R; ++i) cout << P[i] << ' ' << Q[i] << '\n';
}
signed main(){
starburst
int t = 1; //cin >> t;
while(t--) solve();
}*/
Compilation message
sorting.cpp: In function 'long long int findSwapPairs(long long int, long long int*, long long int, long long int*, long long int*, long long int*, long long int*)':
sorting.cpp:52:18: warning: declaration of 'x' shadows a previous local [-Wshadow]
52 | for(auto x:cur) cout << x << ' ';
| ^
sorting.cpp:49:13: note: shadowed declaration is here
49 | int x = X[id], y = Y[id];
| ^
sorting.cpp:61:18: warning: declaration of 'x' shadows a previous local [-Wshadow]
61 | for(auto x:cur) cout << x << ' ';
| ^
sorting.cpp:49:13: note: shadowed declaration is here
49 | int x = X[id], y = Y[id];
| ^
/usr/bin/ld: /tmp/ccItgaAP.o: in function `main':
grader.c:(.text.startup+0x4eb): undefined reference to `findSwapPairs(int, int*, int, int*, int*, int*, int*)'
collect2: error: ld returned 1 exit status
