# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
519162 |
2022-01-25T19:00:00 Z |
tabr |
Sorting (IOI15_sorting) |
C++17 |
|
329 ms |
14496 KB |
#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif
int findSwapPairs(int n, int s[], int m, int x[], int y[], int p[], int q[]) {
int low = -1;
int high = m + 1;
while (high - low > 1) {
int mid = (high + low) >> 1;
vector<int> t(n);
for (int i = 0; i < n; i++) {
t[i] = s[i];
}
for (int i = 0; i < mid; i++) {
swap(t[x[i]], t[y[i]]);
}
vector<pair<int, int>> a;
vector<int> pos(n);
for (int i = 0; i < n; i++) {
pos[t[i]] = i;
}
for (int i = 0; i < n; i++) {
if (t[i] == i) {
continue;
}
int j = pos[i];
a.emplace_back(t[i], t[j]);
swap(t[i], t[j]);
swap(pos[t[i]], pos[t[j]]);
}
if ((int) a.size() <= mid) {
for (int i = 0; i < n; i++) {
t[i] = s[i];
pos[t[i]] = i;
}
for (int i = 0; i < mid; i++) {
swap(t[x[i]], t[y[i]]);
swap(pos[t[x[i]]], pos[t[y[i]]]);
if (i >= (int) a.size()) {
p[i] = q[i] = 0;
} else {
p[i] = pos[a[i].first];
q[i] = pos[a[i].second];
swap(t[p[i]], t[q[i]]);
swap(pos[t[p[i]]], pos[t[q[i]]]);
}
}
high = mid;
} else {
low = mid;
}
}
return high;
}
#ifdef tabr
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
return 0;
}
#endif
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
0 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
0 ms |
204 KB |
Output is correct |
8 |
Correct |
0 ms |
204 KB |
Output is correct |
9 |
Correct |
0 ms |
204 KB |
Output is correct |
10 |
Correct |
0 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
0 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
296 KB |
Output is correct |
4 |
Correct |
1 ms |
292 KB |
Output is correct |
5 |
Correct |
1 ms |
280 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
0 ms |
204 KB |
Output is correct |
8 |
Correct |
0 ms |
204 KB |
Output is correct |
9 |
Correct |
0 ms |
204 KB |
Output is correct |
10 |
Correct |
0 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
0 ms |
332 KB |
Output is correct |
13 |
Correct |
0 ms |
204 KB |
Output is correct |
14 |
Correct |
0 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
296 KB |
Output is correct |
16 |
Correct |
1 ms |
292 KB |
Output is correct |
17 |
Correct |
1 ms |
280 KB |
Output is correct |
18 |
Correct |
0 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
20 |
Correct |
0 ms |
204 KB |
Output is correct |
21 |
Correct |
1 ms |
540 KB |
Output is correct |
22 |
Correct |
2 ms |
544 KB |
Output is correct |
23 |
Correct |
2 ms |
588 KB |
Output is correct |
24 |
Correct |
2 ms |
552 KB |
Output is correct |
25 |
Correct |
1 ms |
544 KB |
Output is correct |
26 |
Correct |
1 ms |
460 KB |
Output is correct |
27 |
Correct |
1 ms |
460 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
2 ms |
424 KB |
Output is correct |
3 |
Correct |
2 ms |
460 KB |
Output is correct |
4 |
Correct |
1 ms |
432 KB |
Output is correct |
5 |
Correct |
1 ms |
420 KB |
Output is correct |
6 |
Correct |
1 ms |
412 KB |
Output is correct |
7 |
Correct |
2 ms |
428 KB |
Output is correct |
8 |
Correct |
2 ms |
428 KB |
Output is correct |
9 |
Correct |
2 ms |
460 KB |
Output is correct |
10 |
Correct |
2 ms |
428 KB |
Output is correct |
11 |
Correct |
2 ms |
408 KB |
Output is correct |
12 |
Correct |
1 ms |
460 KB |
Output is correct |
13 |
Correct |
2 ms |
460 KB |
Output is correct |
14 |
Correct |
1 ms |
336 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
2 ms |
424 KB |
Output is correct |
3 |
Correct |
2 ms |
460 KB |
Output is correct |
4 |
Correct |
1 ms |
432 KB |
Output is correct |
5 |
Correct |
1 ms |
420 KB |
Output is correct |
6 |
Correct |
1 ms |
412 KB |
Output is correct |
7 |
Correct |
2 ms |
428 KB |
Output is correct |
8 |
Correct |
2 ms |
428 KB |
Output is correct |
9 |
Correct |
2 ms |
460 KB |
Output is correct |
10 |
Correct |
2 ms |
428 KB |
Output is correct |
11 |
Correct |
2 ms |
408 KB |
Output is correct |
12 |
Correct |
1 ms |
460 KB |
Output is correct |
13 |
Correct |
2 ms |
460 KB |
Output is correct |
14 |
Correct |
1 ms |
336 KB |
Output is correct |
15 |
Correct |
231 ms |
13168 KB |
Output is correct |
16 |
Correct |
270 ms |
13332 KB |
Output is correct |
17 |
Correct |
294 ms |
13972 KB |
Output is correct |
18 |
Correct |
99 ms |
12924 KB |
Output is correct |
19 |
Correct |
189 ms |
13636 KB |
Output is correct |
20 |
Correct |
208 ms |
13984 KB |
Output is correct |
21 |
Correct |
195 ms |
13944 KB |
Output is correct |
22 |
Correct |
231 ms |
13576 KB |
Output is correct |
23 |
Correct |
266 ms |
14496 KB |
Output is correct |
24 |
Correct |
312 ms |
14200 KB |
Output is correct |
25 |
Correct |
325 ms |
13892 KB |
Output is correct |
26 |
Correct |
207 ms |
12688 KB |
Output is correct |
27 |
Correct |
188 ms |
12288 KB |
Output is correct |
28 |
Correct |
266 ms |
14084 KB |
Output is correct |
29 |
Correct |
290 ms |
13796 KB |
Output is correct |
30 |
Correct |
146 ms |
11664 KB |
Output is correct |
31 |
Correct |
314 ms |
14040 KB |
Output is correct |
32 |
Correct |
263 ms |
13908 KB |
Output is correct |
33 |
Correct |
329 ms |
14068 KB |
Output is correct |
34 |
Correct |
278 ms |
14128 KB |
Output is correct |
35 |
Correct |
197 ms |
13532 KB |
Output is correct |
36 |
Correct |
78 ms |
10816 KB |
Output is correct |
37 |
Correct |
315 ms |
14480 KB |
Output is correct |
38 |
Correct |
301 ms |
13892 KB |
Output is correct |
39 |
Correct |
307 ms |
14004 KB |
Output is correct |