oj.uz

Submission #46934

# Submission time Handle Problem Language Result Execution time Memory
46934 2018-04-25T07:32:11 Z mAng0 Sorting (IOI15_sorting) C++17
36 / 100
 4 ms 512 KB 
// #include <cstdio>
#include "sorting.h"
using namespace std;


int S2[200001], vis[200001];
int perm[200001], inv[200001];
//int N, M;
//int S[200001];
//int X[1000001], Y[1000001];
//int P[1000001], Q[1000001];

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
//int findSwapPairs(){
    int ss = 0, ee = M, R = 0, now = 0;
    while(ss <= ee){
        int mid = (ss+ee) / 2;
        for(int i=0;i<N;i++){
            S2[i] = S[i];
            vis[i] = 0;
        }
        for(int i=now;i<mid;i++){
            int tmp = S2[X[i]]; S2[X[i]] = S2[Y[i]]; S2[Y[i]] = tmp;
        }
        int cnt = 0;
        for(int i=0;i<N;i++){
            if(vis[i]) continue;
            int ii = S2[i];
            while(ii != i){
                vis[ii] = 1;
                cnt++;
                ii = S2[ii];
            }
        }
        if(cnt <= mid){
            R = mid;
            ee = mid - 1;
        }else{
            now = mid;
            for(int i=0;i<N;i++) S[i] = S2[i];
            ss = mid + 1;
        }
    }
    for(int i=now;i<R;i++){
        int tmp = S[X[i]]; S[X[i]] = S[Y[i]]; S[Y[i]] = tmp;
    }
    for(int i=0;i<N;i++){
        //printf("%d ", S[i]);
        vis[i] = 0;
        perm[i] = i;
        inv[i] = i;
    }
    //printf("\n");
    int cnt = 0;
    for(int i=0;i<N;i++){
        if(vis[i]) continue;
        while(S[i] != i){
            vis[S[i]] = 1;
            P[cnt] = i; Q[cnt] = S[i];
            int nxt = S[i];
            S[i] = S[nxt];
            S[nxt] = nxt;
            cnt++;
        }
    }
    /*
    for(int i=0;i<R;i++){
        printf("%d %d\n", P[i], Q[i]);
    }
    */
    for(int i=R-2;i>=0;i--){
        int tmp;
        int p1 = inv[X[i+1]], q1 = inv[Y[i+1]];
        tmp = perm[p1]; perm[p1] = perm[q1]; perm[q1] = tmp;
        tmp = inv[p1]; inv[p1] = inv[q1]; inv[q1] = tmp;
        P[i] = perm[P[i]]; Q[i] = perm[Q[i]];
    }
    return R;
}
/*
int main(){
    int n;
    scanf("%d",&N);
    for(int i=0;i<N;i++) scanf("%d", &S[i]);
    scanf("%d",&M);
    for(int i=0;i<M;i++) scanf("%d%d",&X[i], &Y[i]);
    int R = findSwapPairs();
    printf("%d\n", R);
    for(int i=0;i<R;i++){
        printf("%d %d\n", P[i], Q[i]);
    }
}
*/

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 356 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 356 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 256 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 356 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 356 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 3 ms 384 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 256 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 356 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 356 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 3 ms 384 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Correct 2 ms 256 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 3 ms 384 KB Output is correct
17 Correct 2 ms 384 KB Output is correct
18 Correct 2 ms 256 KB Output is correct
19 Correct 2 ms 256 KB Output is correct
20 Correct 2 ms 384 KB Output is correct
21 Incorrect 4 ms 384 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -