Submission #1269359

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269359		vtnoo	Sorting (IOI15_sorting)	C++20	20 / 100	1 ms	328 KiB

sorting

#include <bits/stdc++.h>
using namespace std;

const int MAXN=200000;
int E[MAXN], I[MAXN], S[MAXN], F[MAXN];

int findSwapPairs(int N, int S_[], int M, int X[], int Y[], int P[], int Q[]){
    if(is_sorted(S_, S_+N)){
        return 0;
    }
    for(int i=0;i<N;i++){
        S[i]=S_[i];
        E[S[i]]=i;
        F[i]=i;
    }
    for(int i=0;i<M;i++){
        swap(F[X[i]], F[Y[i]]);
    }
    for(int i=0;i<N;i++){
        I[F[i]]=i;
    }
    for(int i=0;i<M;i++)P[i]=Q[i]=0;
    int u=0, j=0, ans=0;
    for(int i=0;i<M;i++){
        int a=X[i], b=Y[i];
        swap(S[a], S[b]);
        swap(I[a], I[b]);
        F[I[a]]=E[S[a]]=a;
        F[I[b]]=E[S[b]]=b;
        while(u<N&&E[u]==F[u])u++;
        if(u==N)continue;
        ans++;
        int aa=E[u], bb=F[u];
        P[j]=aa;
        Q[j]=bb;
        swap(S[aa], S[bb]);
        E[S[aa]]=aa;
        E[S[bb]]=bb;
        j++;
    }
    /* for(int i=0;i<N;i++){
        cout<<S[i]<<" ";
    }
    cout<<endl; */
    return ans;
}
 

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