Käännöt

input/code.cpp:3:9: fatal error: windows.h: No such file or directory
    3 | #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;
}

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

void solve4(){
	if(inv%2==1){
		cout<<"NO"<<endl;
		return;
	}
	
	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;
	
	int cnt=0;
	while(!complete&&m<=1000000){
		cnt++;
		int 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;
		if(cnt%3==0){
			reverse4(l-1);
			appendAns(l-1);
			reverse4(l+1);
			appendAns(l+1);
			reverse4(l-2);
			appendAns(l-2);
			reverse4(l-1);
			appendAns(l-1);
			reverse4(l-2);
			appendAns(l-2);
			reverse4(l-1);
			appendAns(l-1);
			reverse4(l-3);
			appendAns(l-3);
			reverse4(l-2);
			appendAns(l-2);
			reverse4(l-1);
			appendAns(l-1);
			reverse4(l+1);
			appendAns(l+1);
			reverse4(l);
			appendAns(l);
			reverse4(l-3);
			appendAns(l-3);
			reverse4(l);
			appendAns(l);
			reverse4(l-1);
			appendAns(l-1);
			continue;
		}
		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(m>1000000){
		cout<<"NO"<<endl;
		return;
	}
//	debug();
	cout<<"YES"<<endl;
	cout<<m<<endl;
	for(int i=1;i<=m;i++){
		cout<<ansList[i]<<" ";
	}
}
//----------------k=5----------------//
bool inOrderLast6(){
	for(int i=n-5;i<n;i++){
		if(a[i+1]<a[i])return false;
	}
	return true;
}
void reverse5(int p){
	swap(b[a[p]],b[a[p+4]]);
	swap(a[p],a[p+4]);
	swap(b[a[p+1]],b[a[p+3]]);
	swap(a[p+1],a[p+3]);
}
void shuffle(){
	int pos=rand()%6+n-5;
	reverse5(pos);
	appendAns(pos);
}
void swap2(int pos){
//	cout<<endl;
	reverse5(pos-3);
	appendAns(pos-3);
	reverse5(pos-1);
	appendAns(pos-1);
	reverse5(pos-3);
	appendAns(pos-3);
	reverse5(pos-2);
	appendAns(pos-2);
	reverse5(pos-1);
	appendAns(pos-1);
//	cout<<endl;
}

void solve5(){
	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;
		}
	}
	if(inOrder()){
		cout<<"YES\n0\n";
		return;
	}
	if(n==5){
		reverse5(1);
		appendAns(1);
		if(!inOrder()){
			cout<<"NO"<<endl;
			return;
		}
		cout<<"YES"<<endl;
		cout<<1<<endl;
		return;
	}
	if(n==6){
		bool complete=false;
		int l=1;
		for(int i=1;i<=3;i++){
			reverse5(l);
			appendAns(l);
			if(inOrder()){
				complete=true;
				break;
			}
			reverse5(l+1);
			appendAns(l+1);
			if(inOrder()){
				complete=true;
				break;
			}
		}
		if(!complete){
			cout<<"NO"<<endl;
			return;
		}
		cout<<"YES"<<endl;
		for(int i=1;i<=m;i++){
			cout<<ansList[i]<<" ";
		}
		return;
	}
	for(int i=1;i<=n-6;i++){
		if(b[i]==i)continue;
		//o....x...
		while(b[i]-i>=5){
			int pos=b[i]-4;
			reverse5(pos);
			appendAns(pos);
		}
		//o.x....
		if(b[i]-i==2){
			int pos=b[i]-1;
			reverse5(pos);
			appendAns(pos);
		}
		if(b[i]-i==4){
			reverse5(i);
			appendAns(i);
		}
	}
	bool complete=false;
	int l=n-5;
	int cnt=0;
	while(!complete&&m<=1000000){
		int cmpM=m;
		cnt++;
		for(int i=1;i<=3;i++){
			reverse5(l);
			appendAns(l);
			if(inOrderLast6()){
				complete=true;
				break;
			}
			reverse5(l+1);
			appendAns(l+1);
			if(inOrderLast6()){
				complete=true;
				break;
			}
		}
		if(complete)break;
		if(cnt%3==0){
			shuffle();
			continue;
		}
		if(inOrder()){
			break;
		}
		m=cmpM;
		swap2(l);
		swap2(l+2);
		if(inOrder()){
			break;
		}
	}
	
	if(m>1000000){
		cout<<"NO"<<endl;
		return;
	}
//	debug();
	cout<<"YES"<<endl;
	cout<<m<<endl;
	for(int i=1;i<=m;i++){
		cout<<ansList[i]<<" ";
	}
}
//-----------------------------------//

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;
}