#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, advX, advY;
vector<PII> swapPlan;
bool checkRounds(int rounds) {
swapPlan.clear();
swapPlan.resize(rounds, MP(0, 0));
// slotMapping[i] = plate at slot i
vector<int> slotMapping(sizeN);
// currApple[i] = apple at slot i
vector<int> currApple(sizeN);
// positionOfApple[v] = slot of apple v
vector<int> positionOfApple(sizeN);
// platePosition[p] = slot of plate p
vector<int> platePosition(sizeN);
for (int i = 0; i < sizeN; ++i) {
currApple[i] = initialApples[i];
positionOfApple[currApple[i]] = i;
slotMapping[i] = i;
platePosition[i] = i;
}
int nextApple = 0;
for (int i = 0; i < rounds; ++i) {
int x = advX[i], y = advY[i];
// adversary swaps plates
swap(slotMapping[x], slotMapping[y]);
platePosition[slotMapping[x]] = x;
platePosition[slotMapping[y]] = y;
// adversary swaps apples
swap(currApple[x], currApple[y]);
positionOfApple[currApple[x]] = x;
positionOfApple[currApple[y]] = y;
// skip correct apples
while (nextApple < sizeN &&
positionOfApple[nextApple] == platePosition[nextApple]) {
++nextApple;
}
if (nextApple == sizeN) break;
// fix nextApple
int from = positionOfApple[nextApple];
int to = platePosition[nextApple];
swapPlan[i] = MP(from, to);
swap(currApple[from], currApple[to]);
positionOfApple[currApple[from]] = from;
positionOfApple[currApple[to]] = to;
}
// final check
while (nextApple < sizeN &&
positionOfApple[nextApple] == platePosition[nextApple]) {
++nextApple;
}
return nextApple == sizeN;
}
int findSwapPairs(int N, int S[], int M,
int X[], int Y[],
int P[], int Q[])
{
sizeN = N;
initialApples.assign(S, S + N);
advX.assign(X, X + M);
advY.assign(Y, Y + M);
int lo = -1, hi = M + 1;
while (lo + 1 < hi) {
int mid = (lo + hi) >> 1;
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;
}
