#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
#define PII pair<int, int>
#define MP make_pair
#define FI first
#define SE second
int sizeN;
vector<int> initialApples, adversaryX, adversaryY;
vector<PII> swapPlan;
// Check if we can finish in 'rounds' rounds, filling swapPlan
bool checkRounds(int rounds) {
swapPlan.clear();
swapPlan.resize(rounds, MP(0, 0));
vector<int> plateAtSlot(sizeN), appleSlot(sizeN), currApples(sizeN);
vector<int> slotOfPlate(sizeN), desiredSlot(sizeN);
// Initialize current apples and appleSlot
for (int i = 0; i < sizeN; ++i) {
currApples[i] = initialApples[i];
appleSlot[currApples[i]] = i;
plateAtSlot[i] = i;
}
// Pre-simulate adversary's plate swaps
for (int i = 0; i < rounds; ++i) {
swap(plateAtSlot[adversaryX[i]], plateAtSlot[adversaryY[i]]);
}
// Build slotOfPlate and desiredSlot maps
for (int slot = 0; slot < sizeN; ++slot) {
slotOfPlate[plateAtSlot[slot]] = slot;
}
for (int plate = 0; plate < sizeN; ++plate) {
desiredSlot[plate] = slotOfPlate[plate];
}
int nextApple = 0;
for (int i = 0; i < rounds; ++i) {
// Adversary swaps apples at slots
int x = adversaryX[i], y = adversaryY[i];
swap(currApples[x], currApples[y]);
appleSlot[currApples[x]] = x;
appleSlot[currApples[y]] = y;
// Skip already-correct apples
while (nextApple < sizeN &&
appleSlot[nextApple] == desiredSlot[nextApple]) {
++nextApple;
}
if (nextApple == sizeN) break;
// Swap the next mis-placed apple into its correct slot
int from = appleSlot[nextApple];
int to = desiredSlot[nextApple];
swapPlan[i] = MP(from, to);
swap(currApples[from], currApples[to]);
appleSlot[currApples[from]] = from;
appleSlot[currApples[to]] = to;
}
// Final check
while (nextApple < sizeN &&
appleSlot[nextApple] == desiredSlot[nextApple]) {
++nextApple;
}
return nextApple == sizeN;
}
// Main API: fill P[]/Q[] with up to M swaps, return number of rounds used
int findSwapPairs(int N, int S[], int M,
int X[], int Y[],
int P[], int Q[])
{
sizeN = N;
initialApples.clear();
adversaryX.clear();
adversaryY.clear();
initialApples.resize(sizeN);
adversaryX.resize(M);
adversaryY.resize(M);
for (int i = 0; i < sizeN; ++i) initialApples[i] = S[i];
for (int i = 0; i < M; ++i) {
adversaryX[i] = X[i];
adversaryY[i] = Y[i];
}
int lo = -1, hi = M + 1;
while (lo + 1 < hi) {
int mid = (lo + hi) / 2;
if (checkRounds(mid)) hi = mid;
else lo = mid;
}
checkRounds(hi);
for (int i = 0; i < hi; ++i) {
P[i] = swapPlan[i].FI;
Q[i] = swapPlan[i].SE;
}
return hi;
}
