#include <vector>
#include <numeric>
#include <algorithm>
#include "sorting.h"
using namespace std;
/**
* Validates if the array can be sorted in exactly 'steps' rounds.
* Returns true if possible, and populates user_P and user_Q with the swaps.
*/
bool can_sort(int N, int S[], int steps, int fixed_X[], int fixed_Y[], int user_P[], int user_Q[]) {
vector<int> current_arr(S, S + N);
vector<int> target_arr(S, S + N);
// 1. Pre-calculate the state of the array after ALL 'steps' fixed swaps occur.
for (int i = 0; i < steps; ++i) {
swap(target_arr[fixed_X[i]], target_arr[fixed_Y[i]]);
}
// 2. Track where values are in the current array and where they need to go.
// val_to_pos: current_arr[pos] = value
// val_to_target_pos: target_arr[target_pos] = value
vector<int> val_to_pos(N), val_to_target_pos(N);
for (int i = 0; i < N; ++i) {
val_to_pos[current_arr[i]] = i;
val_to_target_pos[target_arr[i]] = i;
}
int needed_val = 0;
for (int i = 0; i < steps; ++i) {
// Step A: Apply the fixed swap for this round
int fx = fixed_X[i], fy = fixed_Y[i];
// Update current_arr and the value-to-position map
swap(val_to_pos[current_arr[fx]], val_to_pos[current_arr[fy]]);
swap(current_arr[fx], current_arr[fy]);
// Step B: Find the next element that isn't in its final sorted position
while (needed_val < N && val_to_target_pos[needed_val] == needed_val) {
needed_val++;
}
if (needed_val < N) {
// We need 'needed_val' to eventually end up at 'needed_val'.
// In the current target array, some value 'v' is currently at 'needed_val'.
int pos_of_needed = val_to_pos[needed_val];
int val_at_target_loc = target_arr[needed_val];
int pos_of_val_at_target_loc = val_to_pos[val_at_target_loc];
user_P[i] = pos_of_needed;
user_Q[i] = pos_of_val_at_target_loc;
// Step C: Update target_arr to reflect the swap we just made
// This effectively "resolves" one node in the cycle decomposition.
int v1 = current_arr[user_P[i]];
int v2 = current_arr[user_Q[i]];
swap(target_arr[val_to_target_pos[v1]], target_arr[val_to_target_pos[v2]]);
swap(val_to_target_pos[v1], val_to_target_pos[v2]);
// Update current_arr for the next round's simulation
swap(val_to_pos[current_arr[user_P[i]]], val_to_pos[current_arr[user_Q[i]]]);
swap(current_arr[user_P[i]], current_arr[user_Q[i]]);
} else {
// Already sorted, perform a redundant swap
user_P[i] = user_Q[i] = 0;
}
}
// Check if the final state of target_arr is identity (0, 1, 2...)
for (int i = 0; i < N; ++i) {
if (target_arr[i] != i) return false;
}
return true;
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
int low = 0, high = M;
int best_t = M;
while (low <= high) {
int mid = low + (high - low) / 2;
// We use a temporary buffer to avoid corrupting P/Q during binary search
vector<int> temp_P(mid), temp_Q(mid);
if (can_sort(N, S, mid, X, Y, temp_P.data(), temp_Q.data())) {
best_t = mid;
high = mid - 1;
} else {
low = mid + 1;
}
}
// Fill the actual output arrays with the winning strategy
can_sort(N, S, best_t, X, Y, P, Q);
return best_t;
}
