#include <bits/stdc++.h>
#include "sorting.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 6e5 + 10;
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define fillchar(a, s) memset((a), (s), sizeof(a))
int N;
int M;
int S[MAXN];
int X[MAXN], Y[MAXN];
int P[MAXN], Q[MAXN];
bool vis[MAXN];
int cur[MAXN], ind[MAXN];
bool moo (int nsteps, bool dbg = false) {
for (int i = 0; i < N; i++) {
cur[i] = S[i];
}
for (int i = 0; i < nsteps; i++) {
swap(cur[X[i]], cur[Y[i]]);
}
//check if you can do it
vector<pii> swaps;
for (int i = 0; i < N; i++) {
while (cur[i] != i) {
swaps.push_back({cur[i], cur[cur[i]]});
swap(cur[i], cur[cur[i]]);
}
}
if (swaps.size() > nsteps) {
return false;
}
while (swaps.size() < nsteps) {
swaps.push_back({0, 0});
}
for (int i = 0; i < N; i++) {
cur[i] = S[i];
ind[cur[i]] = i;
}
for (int i = 0; i < nsteps; i++) {
int x = X[i], y = Y[i];
swap(ind[cur[x]], ind[cur[y]]);
swap(cur[x], cur[y]);
x = swaps[i].fi;
y = swaps[i].se;
P[i] = ind[x];
Q[i] = ind[y];
swap(cur[ind[x]], cur[ind[y]]);
swap(ind[x], ind[y]);
}
return true;
}
int findSwapPairs (int nn, int ss[], int mm, int xx[], int yy[], int ansp[], int ansq[]) {
N = nn;
for (int i = 0; i < N; i++) {
S[i] = ss[i];
}
M = mm;
for (int i = 0; i < M; i++) {
X[i] = xx[i];
Y[i] = yy[i];
if (X[i] > Y[i]) {
swap(X[i], Y[i]);
}
}
int lo = -1, hi = M; //lo is not possible, hi is
while (hi - lo > 1) {
int mid = (lo + hi) / 2;
if (moo(mid)) {
hi = mid;
} else {
lo = mid;
}
}
moo(hi);
for (int i = 0; i < hi; i++) {
ansp[i] = P[i];
ansq[i] = Q[i];
}
return hi;
}
Compilation message
sorting.cpp: In function 'bool moo(int, bool)':
sorting.cpp:43:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (swaps.size() > nsteps) {
~~~~~~~~~~~~~^~~~~~~~
sorting.cpp:47:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (swaps.size() < nsteps) {
~~~~~~~~~~~~~^~~~~~~~
sorting.cpp:25:34: warning: unused parameter 'dbg' [-Wunused-parameter]
bool moo (int nsteps, bool dbg = false) {
^~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
3 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
3 ms |
384 KB |
Output is correct |
5 |
Correct |
3 ms |
384 KB |
Output is correct |
6 |
Correct |
3 ms |
384 KB |
Output is correct |
7 |
Correct |
3 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
3 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
3 ms |
384 KB |
Output is correct |
5 |
Correct |
3 ms |
384 KB |
Output is correct |
6 |
Correct |
3 ms |
384 KB |
Output is correct |
7 |
Correct |
3 ms |
384 KB |
Output is correct |
8 |
Correct |
3 ms |
384 KB |
Output is correct |
9 |
Correct |
3 ms |
384 KB |
Output is correct |
10 |
Correct |
3 ms |
512 KB |
Output is correct |
11 |
Correct |
3 ms |
384 KB |
Output is correct |
12 |
Correct |
3 ms |
512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
3 ms |
384 KB |
Output is correct |
5 |
Correct |
3 ms |
512 KB |
Output is correct |
6 |
Correct |
4 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
3 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
3 ms |
384 KB |
Output is correct |
5 |
Correct |
3 ms |
384 KB |
Output is correct |
6 |
Correct |
3 ms |
384 KB |
Output is correct |
7 |
Correct |
3 ms |
384 KB |
Output is correct |
8 |
Correct |
3 ms |
384 KB |
Output is correct |
9 |
Correct |
3 ms |
384 KB |
Output is correct |
10 |
Correct |
3 ms |
512 KB |
Output is correct |
11 |
Correct |
3 ms |
384 KB |
Output is correct |
12 |
Correct |
3 ms |
512 KB |
Output is correct |
13 |
Correct |
2 ms |
384 KB |
Output is correct |
14 |
Correct |
2 ms |
384 KB |
Output is correct |
15 |
Correct |
2 ms |
384 KB |
Output is correct |
16 |
Correct |
3 ms |
384 KB |
Output is correct |
17 |
Correct |
3 ms |
512 KB |
Output is correct |
18 |
Correct |
4 ms |
384 KB |
Output is correct |
19 |
Correct |
2 ms |
384 KB |
Output is correct |
20 |
Correct |
2 ms |
384 KB |
Output is correct |
21 |
Correct |
4 ms |
896 KB |
Output is correct |
22 |
Correct |
5 ms |
768 KB |
Output is correct |
23 |
Correct |
4 ms |
768 KB |
Output is correct |
24 |
Correct |
4 ms |
768 KB |
Output is correct |
25 |
Correct |
4 ms |
768 KB |
Output is correct |
26 |
Correct |
4 ms |
768 KB |
Output is correct |
27 |
Correct |
4 ms |
768 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
512 KB |
Output is correct |
2 |
Correct |
4 ms |
640 KB |
Output is correct |
3 |
Correct |
4 ms |
640 KB |
Output is correct |
4 |
Correct |
4 ms |
512 KB |
Output is correct |
5 |
Correct |
3 ms |
640 KB |
Output is correct |
6 |
Correct |
3 ms |
512 KB |
Output is correct |
7 |
Correct |
3 ms |
640 KB |
Output is correct |
8 |
Correct |
3 ms |
640 KB |
Output is correct |
9 |
Correct |
5 ms |
640 KB |
Output is correct |
10 |
Correct |
4 ms |
640 KB |
Output is correct |
11 |
Correct |
3 ms |
640 KB |
Output is correct |
12 |
Correct |
5 ms |
640 KB |
Output is correct |
13 |
Correct |
5 ms |
640 KB |
Output is correct |
14 |
Correct |
3 ms |
512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
512 KB |
Output is correct |
2 |
Correct |
4 ms |
640 KB |
Output is correct |
3 |
Correct |
4 ms |
640 KB |
Output is correct |
4 |
Correct |
4 ms |
512 KB |
Output is correct |
5 |
Correct |
3 ms |
640 KB |
Output is correct |
6 |
Correct |
3 ms |
512 KB |
Output is correct |
7 |
Correct |
3 ms |
640 KB |
Output is correct |
8 |
Correct |
3 ms |
640 KB |
Output is correct |
9 |
Correct |
5 ms |
640 KB |
Output is correct |
10 |
Correct |
4 ms |
640 KB |
Output is correct |
11 |
Correct |
3 ms |
640 KB |
Output is correct |
12 |
Correct |
5 ms |
640 KB |
Output is correct |
13 |
Correct |
5 ms |
640 KB |
Output is correct |
14 |
Correct |
3 ms |
512 KB |
Output is correct |
15 |
Correct |
377 ms |
20032 KB |
Output is correct |
16 |
Correct |
492 ms |
20532 KB |
Output is correct |
17 |
Correct |
355 ms |
21800 KB |
Output is correct |
18 |
Correct |
101 ms |
17272 KB |
Output is correct |
19 |
Correct |
169 ms |
19936 KB |
Output is correct |
20 |
Correct |
210 ms |
20644 KB |
Output is correct |
21 |
Correct |
232 ms |
20624 KB |
Output is correct |
22 |
Correct |
405 ms |
21656 KB |
Output is correct |
23 |
Correct |
388 ms |
22092 KB |
Output is correct |
24 |
Correct |
465 ms |
22224 KB |
Output is correct |
25 |
Correct |
401 ms |
22128 KB |
Output is correct |
26 |
Correct |
229 ms |
20396 KB |
Output is correct |
27 |
Correct |
270 ms |
19828 KB |
Output is correct |
28 |
Correct |
390 ms |
21736 KB |
Output is correct |
29 |
Correct |
400 ms |
21836 KB |
Output is correct |
30 |
Correct |
181 ms |
19276 KB |
Output is correct |
31 |
Correct |
421 ms |
22220 KB |
Output is correct |
32 |
Correct |
400 ms |
21528 KB |
Output is correct |
33 |
Correct |
459 ms |
22392 KB |
Output is correct |
34 |
Correct |
403 ms |
22008 KB |
Output is correct |
35 |
Correct |
224 ms |
19992 KB |
Output is correct |
36 |
Correct |
71 ms |
18512 KB |
Output is correct |
37 |
Correct |
379 ms |
23212 KB |
Output is correct |
38 |
Correct |
361 ms |
22032 KB |
Output is correct |
39 |
Correct |
301 ms |
22524 KB |
Output is correct |