# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
387248 | 2021-04-08T07:34:29 Z | alireza_kaviani | Sorting (IOI15_sorting) | C++11 | 929 ms | 35808 KB |
#include <bits/stdc++.h> #include "sorting.h" using namespace std; #define SZ(x) int((x).size()) const int MAXN = 2e5 + 10; int A[MAXN] , to[MAXN] , pos[MAXN] , mark[MAXN] , p[MAXN] , q[MAXN]; vector<int> vec , adj[MAXN]; void DFS(int v){ mark[v] = 1; vec.push_back(v); // cout << v << endl; for(int u : adj[v]){ // cout << v << ' ' << u << endl; if(!mark[u]) DFS(u); } } int check(int N, int M, int X[], int Y[]) { // cout << endl << "==========" << endl << M << endl; int cnt = 0; fill(p , p + MAXN , 0); fill(q , q + MAXN , 0); fill(mark , mark + MAXN , 0); for(int i = 0 ; i < N ; i++) adj[i].clear(); for(int i = 0 ; i < N ; i++) to[i] = pos[i] = i; for(int i = 0 ; i < M ; i++){ swap(A[X[i]] , A[Y[i]]); } for(int i = 0 ; i < N ; i++){ // cout << A[i] << ' '; adj[i].push_back(A[i]); } // cout << endl; for(int i = 0 ; i < N ; i++){ if(!mark[i]){ vec.clear(); DFS(i); // cout << "DFS " << i << ' ' << SZ(vec) << endl; // for(int j : vec) cout << j << ' '; for(int j = 1 ; j < SZ(vec) ; j++){ if(cnt == M) return 0; p[cnt] = vec[0]; q[cnt] = vec[j]; // cout << vec[0] << ' ' << vec[j] << endl; cnt++; } // cout << endl; } } for(int i = M - 1 ; i >= 0 ; i--){ if(i < cnt){ p[i] = to[p[i]]; q[i] = to[q[i]]; } to[pos[X[i]]] = Y[i]; to[pos[Y[i]]] = X[i]; swap(pos[X[i]] , pos[Y[i]]); } return 1; } int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]){ int l = -1 , r = N; while(r - l > 1){ int mid = l + r >> 1; for(int i = 0 ; i < N ; i++) A[i] = S[i]; if(check(N , mid , X , Y)) r = mid; else l = mid; } for(int i = 0 ; i < N ; i++) A[i] = S[i]; int tmp = check(N , r , X , Y); for(int i = 0 ; i < r ; i++){ P[i] = p[i]; Q[i] = q[i]; } return r; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 7404 KB | Output is correct |
2 | Correct | 6 ms | 7404 KB | Output is correct |
3 | Correct | 6 ms | 7404 KB | Output is correct |
4 | Correct | 6 ms | 7404 KB | Output is correct |
5 | Correct | 7 ms | 7404 KB | Output is correct |
6 | Correct | 6 ms | 7404 KB | Output is correct |
7 | Correct | 6 ms | 7404 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 7404 KB | Output is correct |
2 | Correct | 6 ms | 7404 KB | Output is correct |
3 | Correct | 6 ms | 7404 KB | Output is correct |
4 | Correct | 6 ms | 7404 KB | Output is correct |
5 | Correct | 7 ms | 7404 KB | Output is correct |
6 | Correct | 6 ms | 7404 KB | Output is correct |
7 | Correct | 6 ms | 7404 KB | Output is correct |
8 | Correct | 6 ms | 7404 KB | Output is correct |
9 | Correct | 6 ms | 7404 KB | Output is correct |
10 | Correct | 8 ms | 7404 KB | Output is correct |
11 | Correct | 8 ms | 7404 KB | Output is correct |
12 | Correct | 8 ms | 7404 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 7404 KB | Output is correct |
2 | Correct | 6 ms | 7404 KB | Output is correct |
3 | Correct | 8 ms | 7540 KB | Output is correct |
4 | Correct | 8 ms | 7404 KB | Output is correct |
5 | Correct | 8 ms | 7404 KB | Output is correct |
6 | Correct | 6 ms | 7404 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 7404 KB | Output is correct |
2 | Correct | 6 ms | 7404 KB | Output is correct |
3 | Correct | 6 ms | 7404 KB | Output is correct |
4 | Correct | 6 ms | 7404 KB | Output is correct |
5 | Correct | 7 ms | 7404 KB | Output is correct |
6 | Correct | 6 ms | 7404 KB | Output is correct |
7 | Correct | 6 ms | 7404 KB | Output is correct |
8 | Correct | 6 ms | 7404 KB | Output is correct |
9 | Correct | 6 ms | 7404 KB | Output is correct |
10 | Correct | 8 ms | 7404 KB | Output is correct |
11 | Correct | 8 ms | 7404 KB | Output is correct |
12 | Correct | 8 ms | 7404 KB | Output is correct |
13 | Correct | 6 ms | 7404 KB | Output is correct |
14 | Correct | 6 ms | 7404 KB | Output is correct |
15 | Correct | 8 ms | 7540 KB | Output is correct |
16 | Correct | 8 ms | 7404 KB | Output is correct |
17 | Correct | 8 ms | 7404 KB | Output is correct |
18 | Correct | 6 ms | 7404 KB | Output is correct |
19 | Correct | 6 ms | 7404 KB | Output is correct |
20 | Correct | 7 ms | 7404 KB | Output is correct |
21 | Correct | 9 ms | 7532 KB | Output is correct |
22 | Correct | 10 ms | 7532 KB | Output is correct |
23 | Correct | 9 ms | 7532 KB | Output is correct |
24 | Correct | 9 ms | 7532 KB | Output is correct |
25 | Correct | 9 ms | 7532 KB | Output is correct |
26 | Correct | 12 ms | 7532 KB | Output is correct |
27 | Correct | 9 ms | 7532 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 10 ms | 7660 KB | Output is correct |
2 | Correct | 11 ms | 7660 KB | Output is correct |
3 | Correct | 10 ms | 7660 KB | Output is correct |
4 | Correct | 9 ms | 7532 KB | Output is correct |
5 | Correct | 10 ms | 7532 KB | Output is correct |
6 | Correct | 10 ms | 7552 KB | Output is correct |
7 | Correct | 10 ms | 7532 KB | Output is correct |
8 | Correct | 11 ms | 7660 KB | Output is correct |
9 | Correct | 11 ms | 7660 KB | Output is correct |
10 | Correct | 10 ms | 7660 KB | Output is correct |
11 | Correct | 10 ms | 7532 KB | Output is correct |
12 | Correct | 10 ms | 7532 KB | Output is correct |
13 | Correct | 11 ms | 7680 KB | Output is correct |
14 | Correct | 10 ms | 7532 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 10 ms | 7660 KB | Output is correct |
2 | Correct | 11 ms | 7660 KB | Output is correct |
3 | Correct | 10 ms | 7660 KB | Output is correct |
4 | Correct | 9 ms | 7532 KB | Output is correct |
5 | Correct | 10 ms | 7532 KB | Output is correct |
6 | Correct | 10 ms | 7552 KB | Output is correct |
7 | Correct | 10 ms | 7532 KB | Output is correct |
8 | Correct | 11 ms | 7660 KB | Output is correct |
9 | Correct | 11 ms | 7660 KB | Output is correct |
10 | Correct | 10 ms | 7660 KB | Output is correct |
11 | Correct | 10 ms | 7532 KB | Output is correct |
12 | Correct | 10 ms | 7532 KB | Output is correct |
13 | Correct | 11 ms | 7680 KB | Output is correct |
14 | Correct | 10 ms | 7532 KB | Output is correct |
15 | Correct | 735 ms | 30696 KB | Output is correct |
16 | Correct | 791 ms | 32100 KB | Output is correct |
17 | Correct | 880 ms | 34148 KB | Output is correct |
18 | Correct | 206 ms | 20972 KB | Output is correct |
19 | Correct | 544 ms | 23252 KB | Output is correct |
20 | Correct | 649 ms | 27876 KB | Output is correct |
21 | Correct | 603 ms | 26472 KB | Output is correct |
22 | Correct | 827 ms | 27880 KB | Output is correct |
23 | Correct | 859 ms | 34532 KB | Output is correct |
24 | Correct | 888 ms | 34400 KB | Output is correct |
25 | Correct | 863 ms | 33632 KB | Output is correct |
26 | Correct | 526 ms | 23788 KB | Output is correct |
27 | Correct | 509 ms | 23404 KB | Output is correct |
28 | Correct | 895 ms | 32608 KB | Output is correct |
29 | Correct | 759 ms | 24556 KB | Output is correct |
30 | Correct | 357 ms | 22380 KB | Output is correct |
31 | Correct | 879 ms | 34920 KB | Output is correct |
32 | Correct | 833 ms | 33280 KB | Output is correct |
33 | Correct | 876 ms | 34436 KB | Output is correct |
34 | Correct | 844 ms | 25124 KB | Output is correct |
35 | Correct | 531 ms | 23020 KB | Output is correct |
36 | Correct | 130 ms | 21484 KB | Output is correct |
37 | Correct | 929 ms | 35808 KB | Output is correct |
38 | Correct | 838 ms | 34528 KB | Output is correct |
39 | Correct | 888 ms | 35188 KB | Output is correct |