oj.uz

Submission #496705

# Submission time Handle Problem Language Result Execution time Memory
496705 2021-12-21T23:56:55 Z kevin Sorting (IOI15_sorting) C++17
100 / 100
 175 ms 21612 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define vi vector<int>
#define all(x) x.begin(), x.end()
#define ca(v) for(auto i:v) cout<<i<<" ";
#define nl cout<<"\n"

const int MAXN = 5e5 + 5;

int findSwapPairs(int N, int* s, int M, int* X, int* Y, int* P, int* Q){
    int flg = 1;
    for(int i=0; i<N; i++) {
        if(s[i] != i) flg = 0;
    }
    if(flg) return 0;
    int l = 0;
    int r = M-1;
    int ans = M;
    vi S;
    for(int i=0; i<N; i++) S.push_back(s[i]);
    while(l <= r){
        int m = (l+r)/2;
        vi ar = S;
        for(int i=0; i<=m; i++){
            swap(ar[X[i]], ar[Y[i]]);
        }
        int cnt = 0;
        vi vis(N, 0);
        for(int i=0; i<N; i++) {
            if(vis[i]) continue;
            cnt++;
            int q = i;
            while(1){
                vis[q] = 1;
                if(vis[ar[q]]) break;
                q = ar[q];
            }
        }
        cnt = N - cnt;
        if(cnt-1 <= m){
            ans = m;
            r = m-1;
        }
        else l = m+1;
    }
    vi vis(N, 0);
    vi ar = S;
    for(int i=0; i<=ans; i++) swap(ar[X[i]], ar[Y[i]]);
    vi xm, ym;
    int cnt = 0;
    for(int i=0; i<N; i++) {
        if(vis[i]) continue;
        cnt++;
        int q = i;
        while(1){
            vis[q] = 1;
            if(vis[ar[q]]) break;
            xm.push_back(q);
            ym.push_back(ar[q]);
            q = ar[q];
        }
    }
    vector<int> pos(N);
    for(int i=0; i<N; i++) pos[S[i]] = i;
    reverse(xm.begin(), xm.end());
    reverse(ym.begin(), ym.end());
    for(int i=0; i<xm.size(); i++){
        swap(pos[S[X[i]]], pos[S[Y[i]]]);
        swap(S[X[i]], S[Y[i]]);
        P[i] = pos[xm[i]];
        Q[i] = pos[ym[i]];
    }
    return ans+1;
}

Compilation message

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:69:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |     for(int i=0; i<xm.size(); i++){
      |                  ~^~~~~~~~~~

Subtask #1
8.0 / 8.0

# 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 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct

Subtask #2
12.0 / 12.0

# 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 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 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 1 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 0 ms 204 KB Output is correct

Subtask #3
16.0 / 16.0

# 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 1 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 0 ms 204 KB Output is correct

Subtask #4
18.0 / 18.0

# 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 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 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 1 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 0 ms 204 KB Output is correct
19 Correct 0 ms 204 KB Output is correct
20 Correct 0 ms 204 KB Output is correct
21 Correct 1 ms 332 KB Output is correct
22 Correct 1 ms 332 KB Output is correct
23 Correct 1 ms 332 KB Output is correct
24 Correct 1 ms 332 KB Output is correct
25 Correct 1 ms 332 KB Output is correct
26 Correct 1 ms 332 KB Output is correct
27 Correct 1 ms 332 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 424 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 428 KB Output is correct
8 Correct 2 ms 464 KB Output is correct
9 Correct 1 ms 464 KB Output is correct
10 Correct 1 ms 436 KB Output is correct
11 Correct 1 ms 440 KB Output is correct
12 Correct 2 ms 432 KB Output is correct
13 Correct 1 ms 464 KB Output is correct
14 Correct 1 ms 336 KB Output is correct

Subtask #6
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 424 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 428 KB Output is correct
8 Correct 2 ms 464 KB Output is correct
9 Correct 1 ms 464 KB Output is correct
10 Correct 1 ms 436 KB Output is correct
11 Correct 1 ms 440 KB Output is correct
12 Correct 2 ms 432 KB Output is correct
13 Correct 1 ms 464 KB Output is correct
14 Correct 1 ms 336 KB Output is correct
15 Correct 143 ms 18548 KB Output is correct
16 Correct 152 ms 18912 KB Output is correct
17 Correct 170 ms 19924 KB Output is correct
18 Correct 41 ms 13384 KB Output is correct
19 Correct 136 ms 19256 KB Output is correct
20 Correct 142 ms 19748 KB Output is correct
21 Correct 142 ms 19884 KB Output is correct
22 Correct 126 ms 15884 KB Output is correct
23 Correct 152 ms 21524 KB Output is correct
24 Correct 166 ms 21020 KB Output is correct
25 Correct 175 ms 20780 KB Output is correct
26 Correct 136 ms 19780 KB Output is correct
27 Correct 130 ms 19192 KB Output is correct
28 Correct 168 ms 20772 KB Output is correct
29 Correct 159 ms 20308 KB Output is correct
30 Correct 110 ms 18584 KB Output is correct
31 Correct 154 ms 20696 KB Output is correct
32 Correct 145 ms 20612 KB Output is correct
33 Correct 159 ms 21008 KB Output is correct
34 Correct 150 ms 20896 KB Output is correct
35 Correct 134 ms 18996 KB Output is correct
36 Correct 54 ms 17404 KB Output is correct
37 Correct 171 ms 21612 KB Output is correct
38 Correct 159 ms 20760 KB Output is correct
39 Correct 161 ms 20972 KB Output is correct