Submission #71610

#	Time	Username	Problem	Language	Result	Execution time	Memory
71610		mr_banana	Sorting (IOI15_sorting)	C++17	100 / 100	252 ms	16376 KiB

sorting

#include <bits/stdc++.h>
#include "sorting.h"

using namespace std;
const int MN=2e6+100;
int n,a[MN],m,x[MN],y[MN],b[MN];
bool mark[MN];
bool check(int x1){
    for(int i=0;i<n;i++){
        b[i]=a[i];
        mark[i]=0;
    }
    for(int i=0;i<x1;i++){
        swap(b[x[i]],b[y[i]]);
    }
    int cmp=0;
    for(int i=0;i<n;i++){
        if(!mark[i]){
            int x2=i;
            do{
                mark[x2]=1;
                x2=b[x2];
            }while(x2!=i);
            cmp++;
        }
    }
    return (n-cmp)<=x1;
}
int bs(){
    int lo=-1,hi=m;
    while(hi-lo>1){
        int mid=(hi+lo)/2;
        if(check(mid)){
            hi=mid;
        }
        else{
            lo=mid;
        }
    }
    return hi;
}

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int p[], int q[]) {
    n=N;
    for(int i=0;i<n;i++){
        a[i]=S[i];
    }
    m=M;
    for(int i=0;i<m;i++){
        x[i]=X[i],y[i]=Y[i];
    }
    int r=bs();
    for(int i=0;i<n;i++){
        b[i]=a[i];
    }
    for(int i=0;i<r;i++){
        swap(b[x[i]],b[y[i]]);
    }
    int cnt=0;
    for(int i=0;i<n;i++){
        while(b[i]!=i){
            p[cnt]=i;
            q[cnt]=b[i];
            swap(b[i],b[b[i]]);
            cnt++;
        }
    }
    while(cnt<r){
        p[cnt]=0;
        q[cnt]=0;
        cnt++;
    }
    iota(b,b+n,0);
    iota(a,a+n,0);
    for(int i=r-1;i>=0;i--){
        p[i]=a[p[i]];
        q[i]=a[q[i]];
        swap(a[b[x[i]]],a[b[y[i]]]);
        swap(b[x[i]],b[y[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