#include "sorting.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <set>
#include <map>
using namespace std;
typedef long long int ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
#define rep(i, a, b) for (ll i = a; i < b; i++)
#define sz(a) a.size()
#define pb(a) push_back(a)
#define mp(a, b) make_pair(a, b)
ll n, m;
vll s;
vpll mek;
struct node {
ll target;
ll destination;
ll index;
node(ll t, ll d, ll i) {
target = t; destination = d; index = i;
}
};
bool destination_comp(const node& lhs, const node& rhs) {return lhs.destination < rhs.destination;}
bool solve(ll r, vpll& ans) {
vector<node> nodes; // nodes[i].index == i
rep(i, 0, n) nodes.pb(node(0, i, i));
// reverse ermek moves and modify index
for (ll i = r - 1; i >= 0; i--) {
// swap mek[i].first and mek[i].second
swap(nodes[mek[i].first].destination, nodes[mek[i].second].destination);
}
// assign nodes elements
rep(i, 0, n) nodes[i].target = s[i];
vll destination_to_index(n);
rep(i, 0, n) destination_to_index[nodes[i].destination] = i;
vll::iterator d = destination_to_index.begin();
rep(i, 0, r) {
// simulate mek[i] on indices and then check whether nodes[destination_to_index[d]] needs to move anywhere...
// simulate mek swapping indices mek[i]
swap(destination_to_index[nodes[mek[i].first].destination], destination_to_index[nodes[mek[i].second].destination]);
swap(nodes[mek[i].first].index, nodes[mek[i].second].index);
swap(nodes[mek[i].first], nodes[mek[i].second]);
while ((nodes[*d].target == nodes[*d].destination) && (d != destination_to_index.end())) d++;
if (d == destination_to_index.end()) {
ans.pb(mp(0, 0));
} else {
// move nodes[*d] to target
// swap nodes[*d] with nodes[destination_to_index[nodes[*d].target]]
//ll a = nodes[*d].index; // this just equals (*d)
ll b = destination_to_index[nodes[*d].target]; //nodes[destination_to_index[nodes[*d].target]].index;
ans.pb(mp(nodes[*d].index, nodes[b].index));
swap(nodes[*d].target, nodes[b].target);
d++;
}
}
// consider functional graph on nodes:
// edge a-->b iff a.target == b.destination
return (d == destination_to_index.end());
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
n = N;
m = M;
s.resize(n);
mek.resize(m);
rep(i, 0, n) s[i] = S[i];
rep(i, 0, m) mek[i] = mp(X[i], Y[i]);
vpll ans;
ll lowr = -1;
ll highr = m;
while (lowr + 1 < highr) {
ll r = (lowr + highr + 1) / 2;
//cout << "[" << lowr << ", " << highr << "] -> " << r << endl;
if (solve(r, ans)) {
highr = r;
//cout << "high" << endl;
} else {
lowr = r;
//cout << "low" << endl;
}
}
solve(highr, ans);
rep(i, 0, highr) {
P[i] = ans[i].first;
Q[i] = ans[i].second;
}
return highr;
// return R
}
Compilation message
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:106:23: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
106 | P[i] = ans[i].first;
sorting.cpp:107:23: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
107 | Q[i] = ans[i].second;
sorting.cpp:109:12: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
109 | return highr;
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
1108 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
1108 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
