A - Range Swap Editorial by en_translator
Swapping the \(P\)-th through \(Q\)-th terms and \(R\)-th through \(S\) terms makes
\[ A_1,A_2,\ldots, A_{P-1}, A_P,A_{P+1},\ldots, A_{Q-1}, A_Q, A_{Q+1}, \ldots, A_{R-1}, A_R, A_{R+1}, \ldots, A_{S-1}, A_S, A_{S+1}, \ldots, A_{N-1}, A_N \\ \to A_1,A_2,\ldots, A_{P-1}, A_R,A_{R+1},\ldots, A_{S-1}, A_S, A_{Q+1}, \ldots, A_{R-1}, A_P, A_{P+1}, \ldots, A_{Q-1}, A_Q, A_{S+1}, \ldots, A_{N-1}, A_N . \]
Since \(S-R=Q-P\), the indices of the terms that are not swapped are invariant, so it is sufficient to let
\[ B_i= \begin{cases} A_i &(\text{if }i<P ) \\ A_{i+(R-P)} &(\text{if }P\leq i\leq Q ) \\ A_i &(\text{if }Q<i<R ) \\ A_{i+(P-R)} &(\text{if }R\leq i\leq S ) \\ A_i &(\text{if }S<i). \\ \end{cases} \]
This can be implemented with for statements and if statements.
Alternatively, since \(Q-P=S-R\), we can obtain the answer by swapping \(A_{P+i}\) and \(A_{R+i}\) for each \(i=0,1,\ldots, Q-P\).
Sample code in C++ \(1\):
#include <bits/stdc++.h>
using namespace std;
int main() {
int n,p,q,r,s;
int a[101];
cin>>n>>p>>q>>r>>s;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++){
if((p<=i)&&(i<=q))cout<<a[i+r-p];
else if((r<=i)&&(i<=s))cout<<a[i+p-r];
else cout<<a[i];
if(i<n)cout<<" ";
else cout<<endl;
}
return 0;
}
Sample code in C++ \(2\):
#include <bits/stdc++.h>
using namespace std;
int main() {
int n,p,q,r,s;
int a[100];
cin>>n>>p>>q>>r>>s;
for(int i=0;i<n;i++)cin>>a[i];
for(int i=p;i<=q;i++)swap(a[i-1],a[r-p+i-1]);
for(int i=0;i<n;i++){
cout<<a[i];
if(i<(n-1))cout<<" ";
else cout<<endl;
}
return 0;
}
Sample code in Python:
n,p,q,r,s= map(int, input().split())
a=list(map(int, input().split()))
for i in range(p,q+1):
a[i-1],a[r-p+i-1]=a[r-p+i-1],a[i-1]
print(*a)
posted:
last update: