Submission #46937

#	Time	Username	Problem	Language	Result	Execution time	Memory
46937		mAng0	Sorting (IOI15_sorting)	C++17	100 / 100	214 ms	13020 KiB

sorting

#include "sorting.h"

int S2[200001], vis[200001];
int perm[200001], inv[200001];

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++){
        vis[i] = 0;
        perm[i] = i;
        inv[i] = i;
    }
    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=R-2;i>=0;i--){
        int tmp;
        int p1 = X[i+1], q1 = Y[i+1];
        tmp = perm[p1]; perm[p1] = perm[q1]; perm[q1] = tmp;
        int p2 = perm[p1], q2 = perm[q1];
        tmp = inv[p2]; inv[p2] = inv[q2]; inv[q2] = tmp;
        P[i] = inv[P[i]]; Q[i] = inv[Q[i]];
    }
    return R;
}

• Subtask 1: 8 / 8
• Subtask 2: 12 / 12
• Subtask 3: 16 / 16
• Subtask 4: 18 / 18
• Subtask 5: 20 / 20
• Subtask 6: 26 / 26