Submission #46934

#	Time	Username	Problem	Language	Result	Execution time	Memory
46934		mAng0	Sorting (IOI15_sorting)	C++17	36 / 100	4 ms	512 KiB

sorting

// #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 / 8
• Subtask 2: 12 / 12
• Subtask 3: 16 / 16
• Subtask 4: 0 / 18
• Subtask 5: 0 / 20
• Subtask 6: 0 / 26