Official

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: