公式

C - K Swap 解説 by en_translator


When \(K=1\)

When \(K=1\), the operation is what is used in the algorithm called bubble sort.
As bubble sort is a valid sorting algorithm, the answer for \(K=1\) is Yes. Specifically, it is sufficient to let the leftmost value the smallest value, the second leftmost value the second smallest value, \(\ldots\) and so on.

For general \(K\)

Consider \(K\) sequences \(B_0,\ldots,B_{K-1}\) defined as follows:

  • \(B_i=(a_{i+1},a_{K+i+1},a_{2K+i+1},\ldots)\) for \(i=0,\ldots,K-1\)

Then, each operation “swaps adjacent terms of some \(B_i\).”
Since the operations on a sequence \(B_i\) does not affect to those on the others, we may obtain \(A\) after the operations by sorting each of the sequences independently and checking if it is sorted in the ascending order.

Using efficient sorting algorithm

Although we mentioned bubble sort in the beginning of this editorial, using this algorithm to sort the sequence will lead to TLE (execution Time Limit Exceeded). This is because bubble sort has a time complexity of \(\mathrm O(N^2)\), which is too inefficient for the Constraints and the time limit of this problem.
There are some efficient algorithms that runs in an \(\mathrm O(N\log N)\) known, including Merge Sort and Heap Sort, which enable us to get accepted for this problem. You don’t need to implement these algorithms by yourself; for example, in C++, you may write as follows to sort an array in an \(\mathrm O(N\log N)\) time.

sort(a.begin(),a.end());

Sample code

#include <bits/stdc++.h>
using namespace std;

int main() {
    
	int N,K;
	cin>>N>>K;
	
	vector<vector<int>> b(K);
	
	vector<int> a(N);
	for(int i=0;i<N;i++){
		cin>>a[i];
		b[i%K].push_back(a[i]);
	}
	
	for(int i=0;i<K;i++){
		sort(b[i].rbegin(),b[i].rend());
	}
	
	sort(a.begin(),a.end());
	
	vector<int> na;
	for(int i=0;i<N;i++){
		na.push_back(b[i%K].back());
		b[i%K].pop_back();
	}
	
	if(a==na)cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
	
    return 0;
}

投稿日時:
最終更新: