Submission #854001

#	Time	Username	Problem	Language	Result	Execution time	Memory
854001		abcvuitunggio	Sorting (IOI15_sorting)	C++17	100 / 100	134 ms	20700 KiB

sorting

#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
int vis[200001],pos[200001];
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]){
    bool ch=1;
    for (int i=0;i<N;i++)
        ch&=(S[i]==i);
    if (ch)
        return 0;
    int l=0,r=M-1,kq=-1;
    while (l<=r){
        int mid=(l+r)>>1;
        for (int i=0;i<=mid;i++)
            swap(S[X[i]],S[Y[i]]);
        for (int i=0;i<N;i++)
            vis[i]=0;
        int cnt=N;
        for (int i=0;i<N;i++)
            if (!vis[i]){
                cnt--;
                int j=i;
                while (!vis[j]){
                    vis[j]=1;
                    j=S[j];
                }
            }
        for (int i=mid;i>=0;i--)
            swap(S[X[i]],S[Y[i]]);
        if (cnt-1<=mid){
            kq=mid;
            r=mid-1;
        }
        else
            l=mid+1;
    }
    for (int i=0;i<=kq;i++)
        swap(S[X[i]],S[Y[i]]);
    int id=0;
    for (int i=0;i<N;i++){
        while (i!=S[i]){
            P[id]=i;
            Q[id]=S[i];
            swap(S[i],S[S[i]]);
            id++;
        }
        pos[i]=i;
    }
    for (int i=id;i<=kq;i++)
        P[i]=Q[i]=0;
    for (int i=kq;i>=0;i--){
        P[i]=S[P[i]];
        Q[i]=S[Q[i]];
        swap(S[pos[X[i]]],S[pos[Y[i]]]);
        swap(pos[X[i]],pos[Y[i]]);
    }
    return kq+1;
}

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