Käännöt

input/code.cpp:2:9: fatal error: windows.h: No such file or directory
    2 | #include<windows.h>
      |         ^~~~~~~~~~~
compilation terminated.

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

int a[509];
int b[509];
int n,m,k,inv;
int ansList[1000009];

bool inOrder(){
	for(int i=1;i<=n;i++){
		if(a[i]!=i)return false;
	}
	return true;
}

//----------------k=2----------------//
void solve2(){
	cout<<"YES"<<endl;
	int pos;
	for(int i=1;i<=n;i++)if(a[i]!=i){
		for(int j=i+1;j<=n;j++){
			if(a[j]==i)pos=j;
		}
		for(int j=pos-1;j>=i;j--){
			m++;
			ansList[m]=j;
			swap(a[j],a[j+1]);
		}
	}
	cout<<m<<endl;
	for(int i=1;i<=m;i++){
		cout<<ansList[i]<<" ";
	}
}
//----------------k=3----------------//
void solve3(){
	for(int i=1;i<=n;i+=2){
		if(a[i]%2==0){
			cout<<"NO"<<endl;
			return;
		}
	}
	for(int i=2;i<=n;i+=2){
		if(a[i]%2==1){
			cout<<"NO"<<endl;
			return;
		}
	}
	cout<<"YES"<<endl;
	int pos;
	for(int i=1;i<=n;i+=2)if(a[i]!=i){
		for(int j=i+2;j<=n;j++){
			if(a[j]==i)pos=j;
		}
		for(int j=pos-2;j>=i;j-=2){
			m++;
			ansList[m]=j;
			swap(a[j],a[j+2]);
		}
	}
	for(int i=2;i<=n;i+=2)if(a[i]!=i){
		for(int j=i+2;j<=n;j++){
			if(a[j]==i)pos=j;
		}
		for(int j=pos-2;j>=i;j-=2){
			m++;
			ansList[m]=j;
			swap(a[j],a[j+2]);
		}
	}
	cout<<m<<endl;
	for(int i=1;i<=m;i++){
		cout<<ansList[i]<<" ";
	}
}
//----------------k=4----------------//
void reverse4(int p){
	swap(b[a[p]],b[a[p+3]]);
	swap(a[p],a[p+3]);
	swap(b[a[p+1]],b[a[p+2]]);
	swap(a[p+1],a[p+2]);
}

void debug(){
	for(int i=1;i<=n;i++)cout<<a[i]<<" ";
	cout<<endl;
	for(int i=1;i<=n;i++)cout<<b[i]<<" ";
	cout<<endl;
	cout<<endl;
}

void appendAns(int pos){
	m++;
	ansList[m]=pos;
//	Sleep(1000);
//	debug();
}
bool inOrderLast5(){
	for(int i=n-4;i<n;i++){
		if(a[i+1]<a[i])return false;
	}
	return true;
}

void shuffle(){
	for(int i=1;i<=n;i++){
		int pos=rand()%(n-3)+1;
		reverse4(pos);
		appendAns(pos);
	}
}

void solve4(){
	if(inv%2==1){
		cout<<"NO"<<endl;
		return;
	}
	int cmpM;
	while(!inOrder()){
		for(int i=1;i<=n-5;i++){
			if(b[i]==i)continue;
			while(b[i]-i>=4){
				int pos=b[i]-3;
				reverse4(pos);
				appendAns(pos);
			}
			if(b[i]-i==2){
				int pos=b[i]-1;
				reverse4(pos);
				appendAns(pos);
			}
			if(b[i]-i==1){
				int pos=b[i];
				reverse4(pos);
				appendAns(pos);
				ansList[m]=pos;
				pos=b[i]-2;
				reverse4(pos);
				appendAns(pos);
			}
			if(b[i]-i==3){
				reverse4(i);
				appendAns(i);
			}
		}
		
		int l=n-4;
		
		bool complete=false;
		for(int i=1;i<=3;i++){
			cmpM=m;
			for(int i=1;i<=5;i++){
				reverse4(l);
				appendAns(l);
				if(inOrderLast5()){
					complete=true;
					break;
				}
				reverse4(l+1);
				appendAns(l+1);
				if(inOrderLast5()){
					complete=true;
					break;
				}
			}
			if(complete)break;
			m=cmpM;
			reverse4(l-1);
			appendAns(l-1);
			reverse4(l);
			appendAns(l);
			reverse4(l-1);
			appendAns(l-1);
			reverse4(l);
			appendAns(l);
			reverse4(l+1);
			appendAns(l+1);
			reverse4(l-1);
			appendAns(l-1);
		}
		if(complete)break;
		shuffle();
	}
	
		
	
//	debug();
	cout<<"YES"<<endl;
	for(int i=1;i<=m;i++){
		cout<<ansList[i]<<" ";
	}
}
//----------------k=5----------------//
void solve5(){
	;
}
//-----------------------------------//

int main(){
	srand(unsigned(time(NULL)));
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		for(int j=1;j<i;j++){
			if(a[j]>a[i]){
				inv++;
			}
		}
		b[a[i]]=i;
	}
	
	if(k==2){
		solve2();
	}
	else if(k==3){
		solve3();
	}
	else if(k==4){
		solve4();
	}
	else{
		solve5();
	}
	return 0;
}