Käännöt

input/code.cpp:1:10: fatal error: bits/chrono.h: No such file or directory
    1 | #include <bits/chrono.h>
      |          ^~~~~~~~~~~~~~~
compilation terminated.

#include <bits/chrono.h>
#include<iostream>
#include<bits/stdc++.h>
#include <queue>
#include<unordered_set>
#include<vector>
#include<chrono>
using namespace std;

typedef long long ll;
 
constexpr ll M = 1000000007;
constexpr ll P = (1 << 18);
constexpr int INF = 1e9;

int arr[510] = {0};
int ops[1000001];
int n, k;
int steps = 0; 
string target;

void solve() {
	bool ordered = false;
	//do while? 
	while (!ordered) {
		ordered = true;
		for (int i=1; i<n; i++) {
			switch (k) {
				case 2: 
					if (arr[i] > arr[i+1]) {
						ordered = false;
						swap(arr[i], arr[i+1]);

						ops[steps++] = i;
					}
					break;
				case 3: 
					if (i+2 <= n && (arr[i] > arr[i+2] || arr[i] > arr[i+1])) {
						ordered = false;
						swap(arr[i], arr[i+2]);

						ops[steps++] = i;
					}
					break;
				case 4: 
					if (i+3 <= n) {
						if (i == ops[steps-1]) continue;
						int delta = 0;
						if (arr[i] > arr[i+3]) {
							ordered = false;
							delta++;
						} else delta--;
						if (arr[i+1] > arr[i+2]) {
							ordered = false;
							delta++;
						} else delta--;
						if (arr[i] < arr[i+1]) delta--;
						else delta++;
						if (arr[i+2] < arr[i+3]) delta--;
						else delta++;

						if (delta < 0) {
							for (int j=1; j<=n; j++) {
								cout << arr[j] << " ";
							}	
							cout << endl;
							continue;
						};

						swap(arr[i], arr[i+3]);
						swap(arr[i+1], arr[i+2]);
						ops[steps++] = i;
						cout << steps << ": " << i << endl;
					}

			}
		}
	}
}

unordered_set<string> seen;

bool search() {
	if (steps > 1000000) {
		return false;
	}

	//if (steps % 100000 == 0) cout << steps<< endl;

	string hash = "";
	for (int i=1; i<=n; i++) {
		hash += to_string(arr[i]) + " "; 	
	}

	if (hash == target) return true;

	if (seen.count(hash)) {
	      //cout << "seen" << endl;
	      return false;
	}

	seen.insert(hash);
	//cout << prev << ": " << hash << endl;
	//cout << seen.size() << endl;

	//for (auto i : perm) cout << i << " ";
	//cout << endl;
	//
	priority_queue<pair<int, int>, vector<pair<int,int>>, greater<pair<int,int>>> q;

	for (int i=1; i+3<=n; i++) {
		if (i == ops[steps-1]) continue;

		int delta = 0;
		if (arr[i+3] + 1 == arr[i+4]) delta++; //what if last element
		if (arr[i+4] == arr[i] + 1) delta--;
		if (arr[i-1] + 1 == arr[i]) delta++;
		if (arr[i-1] + 1 == arr[i+3]) delta--;

		q.push({delta, i});

		//if (steps == 0) cout << delta << " ";
	}

	while (!q.empty()) {
		int a = q.top().second; q.pop();

		swap(arr[a], arr[a+3]);
		swap(arr[a+1], arr[a+2]);

		ops[steps++] = a;

		//if (steps == 1) cout << a << endl;
		bool b = search();
		if (b) {
			return b;
		}

		swap(arr[a], arr[a+3]);
		swap(arr[a+1], arr[a+2]);
		steps--;
	}

	return false;
}

int main() {
	cin >> n >> k;

	for (int i=1; i<=n; i++) {
		int d; 
		cin >> d;
		
		int distance = abs(d - i);
		switch (k) {
			case 3: 
				if (distance % 2 == 1) {
					cout << "NO" << endl;
					return 0;
				} break;
//			case 4: 
//				if (d == n || d == 1) {
//					if (distance % 3 != 0) {
//						cout << "NO" << endl;
//						return 0;
//					}	
//				}

		}

		arr[i] = d;
	}


	if (k==2||k==3) solve();
	else {
		for (int i=1; i<=n; i++) {
			target += to_string(i) + " ";
		}
		search();
	}


	if (steps) { 
		cout << "YES" << endl;
		cout << steps << endl;
		for (int i=0; i<steps; i++) {
			cout << ops[i] << " ";
		}
		cout << endl;
	} else {
		cout << "NO" << endl;
	}

	//for (int i=1; i<=n; i++) {
	//	cout << arr[i] << " ";
	//}
	//cout << endl;
}