#include <bits/stdc++.h>
using namespace std;
void findSwapPairs(int n, vector<int> arr, int m, vector<int> x_moves, vector<int> y_moves, vector<int>& x_ans, vector<int>& y_ans){
vector<int> fin_arr, x_todo, y_todo;
auto calc = [&](int mid)->int{
x_todo.clear(); y_todo.clear(); fin_arr = arr;
for(int i = 0; i<mid; ++i)
swap(fin_arr[x_moves[i]], fin_arr[y_moves[i]]);
for(int i = 0; i<n; ++i)
while(fin_arr[i]!=i)
x_todo.push_back(fin_arr[i]), y_todo.push_back(fin_arr[fin_arr[i]]),
swap(fin_arr[i], fin_arr[fin_arr[i]]);
return x_todo.size();
};
int lo = 0, hi = m;
while(lo<hi){
int mid = lo+(hi-lo)/2;
if(calc(mid)<=mid) hi = mid;
else lo = mid+1;
} calc(lo);
x_ans.resize(lo), y_ans.resize(lo);
vector<int> pos(n);
for(int i = 0; i<n; ++i)
pos[arr[i]] = i;
for(int i = 0; i<lo; ++i)
swap(pos[arr[x_moves[i]]], pos[arr[y_moves[i]]]), swap(arr[x_moves[i]], arr[y_moves[i]]),
x_ans[i] = pos[x_todo[i]], y_ans[i] = pos[y_todo[i]],
swap(pos[arr[x_ans[i]]], pos[arr[y_ans[i]]]), swap(arr[x_ans[i]], arr[y_ans[i]]);
}
Compilation message
sorting.cpp: In lambda function:
sorting.cpp:14:27: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
14 | return x_todo.size();
| ~~~~~~~~~~~^~
/usr/bin/ld: /tmp/ccWY6iBx.o: in function `main':
grader.c:(.text.startup+0x4eb): undefined reference to `findSwapPairs(int, int*, int, int*, int*, int*, int*)'
collect2: error: ld returned 1 exit status
