Submission #1172186

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172186		AlgorithmWarrior	Sorting (IOI15_sorting)	C++20	100 / 100	241 ms	13720 KiB

sorting

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

using namespace std;

bool check(int n,int S[],int perm[],int permsuf[],int m,int X[],int Y[],int P[],int Q[],int posp[],int posps[]){
    int i;
    for(i=0;i<n;++i){
        perm[i]=S[i];
        permsuf[i]=i;
        posp[perm[i]]=i;
        posps[i]=i;
    }
    for(i=0;i<m;++i){
        int x=X[i];
        int y=Y[i];
        swap(perm[x],perm[y]);
        swap(posp[perm[x]],posp[perm[y]]);
        swap(permsuf[x],permsuf[y]);
        swap(posps[permsuf[x]],posps[permsuf[y]]);
    }
    int id=0;
    for(i=0;i<m;++i){
        int x=X[i];
        int y=Y[i];
        int px=posps[x];
        int py=posps[y];
        swap(permsuf[px],permsuf[py]);
        swap(posps[x],posps[y]);
        while(id<n && id==perm[id])
            ++id;
        if(id<n){
            int p1=id;
            int p2=perm[id];
            int val1=permsuf[p1];
            int val2=permsuf[p2];
            P[i]=val1;
            Q[i]=val2;
            swap(perm[p1],perm[p2]);
            swap(posp[perm[p1]],posp[perm[p2]]);
        }
        else{
            P[i]=0;
            Q[i]=0;
        }
    }
    for(i=0;i<n;++i)
        if(perm[i]!=i)
            return 0;
    return 1;
}

int const MAX=2e5+5;
int perm[MAX],posp[MAX],permsuf[MAX],posps[MAX];

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    /// (]
    int st=-1,dr=M;
    while(dr-st>1){
        int mij=(st+dr)/2;
        if(check(N,S,perm,permsuf,mij,X,Y,P,Q,posp,posps))
            dr=mij;
        else
            st=mij;
    }
    check(N,S,perm,permsuf,dr,X,Y,P,Q,posp,posps);
    return dr;
}

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