| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 438344 |
2021-06-27T21:10:56 Z |
dutch |
Sorting (IOI15_sorting) |
C++17 |
|
488 ms |
33920 KB |
#include <bits/stdc++.h>
using namespace std;
#include "sorting.h"
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]){
int low = 0, high = M, a[N], g[N];
function<int(int)> find = [&](int v){
bitset<1<<18> vis;
for(int i=0; i<N; ++i){
g[S[i]] = i;
a[i] = S[i];
P[i] = Q[i] = 0;
}
for(int i=0; i<v; ++i) swap(g[a[X[i]]], g[a[Y[i]]]), swap(a[X[i]], a[Y[i]]);
vector<array<int, 2>> t;
function<void(int)> dfs = [&](int u){
vis[u] = 1;
if(!vis[g[u]]) t.push_back({u, g[u]}), dfs(g[u]);
};
for(int i=0; i<N; ++i){
if(!vis[g[S[i]]]) dfs(g[S[i]]);
g[S[i]] = i, a[i] = S[i];
}
for(int i=0; i<min(v, (int)t.size()); ++i){
swap(g[a[X[i]]], g[a[Y[i]]]);
swap(a[X[i]], a[Y[i]]);
P[i] = g[t[i][0]], Q[i] = g[t[i][1]];
}
return t.size();
};
while(low < high){
int v = (low + high) / 2;
if(find(v) <= v) high = v;
else low = v + 1;
}
find(low);
return low;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
288 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
204 KB |
Output is correct |
| 7 |
Correct |
1 ms |
204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
288 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
204 KB |
Output is correct |
| 7 |
Correct |
1 ms |
204 KB |
Output is correct |
| 8 |
Correct |
1 ms |
204 KB |
Output is correct |
| 9 |
Correct |
1 ms |
296 KB |
Output is correct |
| 10 |
Correct |
1 ms |
332 KB |
Output is correct |
| 11 |
Correct |
1 ms |
300 KB |
Output is correct |
| 12 |
Correct |
1 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
296 KB |
Output is correct |
| 4 |
Correct |
1 ms |
304 KB |
Output is correct |
| 5 |
Correct |
1 ms |
332 KB |
Output is correct |
| 6 |
Correct |
1 ms |
296 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
288 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
204 KB |
Output is correct |
| 7 |
Correct |
1 ms |
204 KB |
Output is correct |
| 8 |
Correct |
1 ms |
204 KB |
Output is correct |
| 9 |
Correct |
1 ms |
296 KB |
Output is correct |
| 10 |
Correct |
1 ms |
332 KB |
Output is correct |
| 11 |
Correct |
1 ms |
300 KB |
Output is correct |
| 12 |
Correct |
1 ms |
332 KB |
Output is correct |
| 13 |
Correct |
1 ms |
204 KB |
Output is correct |
| 14 |
Correct |
1 ms |
332 KB |
Output is correct |
| 15 |
Correct |
1 ms |
296 KB |
Output is correct |
| 16 |
Correct |
1 ms |
304 KB |
Output is correct |
| 17 |
Correct |
1 ms |
332 KB |
Output is correct |
| 18 |
Correct |
1 ms |
296 KB |
Output is correct |
| 19 |
Correct |
1 ms |
204 KB |
Output is correct |
| 20 |
Correct |
1 ms |
204 KB |
Output is correct |
| 21 |
Correct |
2 ms |
460 KB |
Output is correct |
| 22 |
Correct |
2 ms |
588 KB |
Output is correct |
| 23 |
Correct |
2 ms |
584 KB |
Output is correct |
| 24 |
Correct |
2 ms |
460 KB |
Output is correct |
| 25 |
Correct |
2 ms |
460 KB |
Output is correct |
| 26 |
Correct |
2 ms |
588 KB |
Output is correct |
| 27 |
Correct |
2 ms |
588 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
588 KB |
Output is correct |
| 2 |
Correct |
3 ms |
588 KB |
Output is correct |
| 3 |
Correct |
3 ms |
588 KB |
Output is correct |
| 4 |
Correct |
2 ms |
460 KB |
Output is correct |
| 5 |
Correct |
2 ms |
560 KB |
Output is correct |
| 6 |
Correct |
2 ms |
460 KB |
Output is correct |
| 7 |
Correct |
3 ms |
460 KB |
Output is correct |
| 8 |
Correct |
3 ms |
588 KB |
Output is correct |
| 9 |
Correct |
3 ms |
588 KB |
Output is correct |
| 10 |
Correct |
3 ms |
588 KB |
Output is correct |
| 11 |
Correct |
3 ms |
460 KB |
Output is correct |
| 12 |
Correct |
2 ms |
496 KB |
Output is correct |
| 13 |
Correct |
3 ms |
588 KB |
Output is correct |
| 14 |
Correct |
2 ms |
460 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
588 KB |
Output is correct |
| 2 |
Correct |
3 ms |
588 KB |
Output is correct |
| 3 |
Correct |
3 ms |
588 KB |
Output is correct |
| 4 |
Correct |
2 ms |
460 KB |
Output is correct |
| 5 |
Correct |
2 ms |
560 KB |
Output is correct |
| 6 |
Correct |
2 ms |
460 KB |
Output is correct |
| 7 |
Correct |
3 ms |
460 KB |
Output is correct |
| 8 |
Correct |
3 ms |
588 KB |
Output is correct |
| 9 |
Correct |
3 ms |
588 KB |
Output is correct |
| 10 |
Correct |
3 ms |
588 KB |
Output is correct |
| 11 |
Correct |
3 ms |
460 KB |
Output is correct |
| 12 |
Correct |
2 ms |
496 KB |
Output is correct |
| 13 |
Correct |
3 ms |
588 KB |
Output is correct |
| 14 |
Correct |
2 ms |
460 KB |
Output is correct |
| 15 |
Correct |
351 ms |
28740 KB |
Output is correct |
| 16 |
Correct |
390 ms |
29600 KB |
Output is correct |
| 17 |
Correct |
454 ms |
32260 KB |
Output is correct |
| 18 |
Correct |
179 ms |
25788 KB |
Output is correct |
| 19 |
Correct |
327 ms |
27916 KB |
Output is correct |
| 20 |
Correct |
325 ms |
25776 KB |
Output is correct |
| 21 |
Correct |
333 ms |
29104 KB |
Output is correct |
| 22 |
Correct |
302 ms |
20164 KB |
Output is correct |
| 23 |
Correct |
374 ms |
33136 KB |
Output is correct |
| 24 |
Correct |
488 ms |
32692 KB |
Output is correct |
| 25 |
Correct |
474 ms |
31268 KB |
Output is correct |
| 26 |
Correct |
352 ms |
19832 KB |
Output is correct |
| 27 |
Correct |
336 ms |
19392 KB |
Output is correct |
| 28 |
Correct |
468 ms |
30828 KB |
Output is correct |
| 29 |
Correct |
416 ms |
20516 KB |
Output is correct |
| 30 |
Correct |
289 ms |
18512 KB |
Output is correct |
| 31 |
Correct |
432 ms |
21056 KB |
Output is correct |
| 32 |
Correct |
365 ms |
31828 KB |
Output is correct |
| 33 |
Correct |
484 ms |
32380 KB |
Output is correct |
| 34 |
Correct |
402 ms |
21496 KB |
Output is correct |
| 35 |
Correct |
323 ms |
26280 KB |
Output is correct |
| 36 |
Correct |
145 ms |
17460 KB |
Output is correct |
| 37 |
Correct |
485 ms |
33920 KB |
Output is correct |
| 38 |
Correct |
461 ms |
32572 KB |
Output is correct |
| 39 |
Correct |
487 ms |
32824 KB |
Output is correct |
