Submission #590134

#	Time	Username	Problem	Language	Result	Execution time	Memory
590134		alirezasamimi100	Sorting (IOI15_sorting)	C++17	100 / 100	175 ms	20820 KiB

sorting

#include "sorting.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
using namespace std;
using pii = pair<int, int>;

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    int l=-1,r=M,k,T[N],f[N],R[N];
    vector<pii> mv;
    while(r-l>1){
        int m=(l+r)>>1;
        k=N;
        memset(f,0,sizeof f);
        for(int i=0; i<N; i++) T[i]=S[i];
        for(int i=0; i<m; i++){
            swap(T[X[i]],T[Y[i]]);
        }
        for(int i=0; i<N; i++){
            if(f[i]) continue;
            k--;
            int x=i;
            while(!f[x]){
                f[x]=1;
                x=T[x];
            }
        }
        if(k<=m) r=m;
        else l=m;
    }
    memset(f,0,sizeof f);
    for(int i=0; i<N; i++){
        T[i]=S[i];
        R[S[i]]=i;
    }
    for(int i=0; i<r; i++){
        swap(T[X[i]],T[Y[i]]);
    }
    for(int i=0; i<N; i++){
        if(f[i]) continue;
        int x=i;
        while(!f[x]){
            f[x]=1;
            x=T[x];
            if(x!=i) mv.pb({i,x});
        }
    }
    int p=0;
    for(int i=0; i<r; i++){
        swap(R[S[X[i]]],R[S[Y[i]]]);
        swap(S[X[i]],S[Y[i]]);
        if(p<(int)mv.size()){
            P[p]=R[mv[p].F];
            Q[p]=R[mv[p].S];
            p++;
        }else{
            P[p]=Q[p]=0;
            p++;
        }
    }
	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