#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define FOR(i, a, b) for (int i = a; i < b; i++)
#define each(a, x) for (auto &x : a)
#define srt(x) sort(all(x))
#define sz(x) (int) (x).size()
#define pb push_back
#define trace(x) for (auto &el : x) cout << el << " "
using pi = pair<int, int>;
using vi = vector<int>;
using vpi = vector<pi>;
struct State {
vi cur; int turn;
vpi steps;
};
bool is_sorted(vi inp) {
int n = sz(inp);
vi to_srt = vi(all(inp));
srt(to_srt);
FOR(i, 0, n) {
if (inp[i] != to_srt[i]) return false;
}
return true;
}
/*
N = length of seq
S = initial seq
M = swaps by ermek
X[i], Y[i] = ith swap of ermek
P[i], Q[i] = swaps player makes
function returns R (number of swaps)
*/
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
int n = N;
int R = 1;
vi initial; FOR(i, 0, n) initial.pb(S[i]);
vpi swaps;
if (is_sorted(initial)) return 0;
swap(initial[X[0]], initial[Y[0]]);
int curturn = 1;
while (!is_sorted(initial)) {
int ni = X[curturn], nj = Y[curturn];
int ini = initial[ni], inj = initial[nj];
// cases:
// initial[nj] = ni and initial[ni] = nj (do our own thing)
// initial[nj] = ni and initial[ni] != nj or vv (swap the correct thing into place so the swap happens)
// neither initial[nj] = ni nor initial[ni] = nj (swap any of them? maybe do our own thing? idk if it matters)
// array is sorted: swap 0 0
if (ini == nj && inj == ni) {
// we can do our own swap here
FOR(i, 0, n) {
if (i == ini || i == inj) continue;
int qidx = 0; while (initial[qidx] != i) qidx++;
if (qidx == ni || qidx == nj) continue;
swaps.pb({i, qidx});
swap(initial[i], initial[qidx]);
break;
}
} else if (ini == nj) {
int idx = 0; while (initial[idx] != ni) idx++;
swaps.pb({idx, nj});
swap(initial[idx], initial[nj]);
} else if (inj == ni) {
int idx = 0; while (initial[idx] != nj) idx++;
swaps.pb({idx, ni});
swap(initial[idx], initial[ni]);
} else {
int idx = 0; while (initial[idx] != ni) idx++;
swaps.pb({idx, nj});
swap(initial[idx], initial[nj]);
// FOR(i, 0, n) {
// if (i == ini || i == inj) continue;
// int qidx = 0; while (initial[qidx] != i) qidx++;
// if (qidx == ni || qidx == nj) continue;
// swaps.pb({i, qidx});
// break;
// }
}
if (is_sorted(initial)) break;
swap(initial[ni], initial[nj]);
curturn++;
}
swaps.pb({0, 0});
// FOR(i, 0, n) {
// int qidx = 0;
// while (initial[qidx] != i) qidx++;
// if (qidx == i || qidx <= 1 || i <= 1) continue;
// swap(initial[X[curturn]], initial[Y[curturn]]);
// curturn++;
// swap(initial[qidx], initial[i]);
// swaps.pb({i, qidx});
// }
R = curturn;
FOR(i, 0, R) {
P[i] = swaps[i].first;
Q[i] = swaps[i].second;
}
// trace(initial); cout << "\n";
// queue<State> q;
// q.push(State{initial, curturn, {}});
// State best;
// while (!q.empty()) {
// auto cur = q.front();
// q.pop();
// if (is_sorted(cur.cur)) {
// best = cur;
// break;
// }
// vi narr = vi(all(cur.cur));
// swap(narr[X[cur.turn]], narr[Y[cur.turn]]);
// FOR(i, 0, n) {
// // if (cur.cur[i] == i) continue;
// FOR(j, i + 1, n) {
// // if (cur.cur[j] == j) continue;
// vi nnarr = vi(all(narr));
// swap(nnarr[i], nnarr[j]);
// vpi nsteps = vpi(all(cur.steps));
// nsteps.pb({i, j});
// q.push(State {nnarr, cur.turn + 1, nsteps});
// }
// }
// }
// int nR = sz(best.steps);
// FOR(i, 0, nR) {
// P[i+R] = best.steps[i].first;
// Q[i+R] = best.steps[i].second;
// }
// R += nR;
return R;
}
