Submission #1269619

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

sorting

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

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

bool can(int e, int N, int S_[], int X[], int Y[], vector<pair<int,int>> &ans){
    ans.clear();
    for(int i=0;i<N;i++){
        S[i]=S_[i];
        E[S[i]]=i;
        F[i]=i;
    }
    for(int i=0;i<e;i++){
        swap(F[X[i]], F[Y[i]]);
    }
    for(int i=0;i<N;i++){
        I[F[i]]=i;
    }
    int u=0;
    for(int i=0;i<e;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;
        int aa=E[u], bb=F[u];
        ans.push_back({aa,bb});
        swap(S[aa], S[bb]);
        E[S[aa]]=aa;
        E[S[bb]]=bb;
    }
    /* for(int i=0;i<N;i++){
        cout<<S[i]<<" ";
    }
    cout<<endl; */
    return u==N;
}

int findSwapPairs(int N, int S_[], int M, int X[], int Y[], int P[], int Q[]){
    if(is_sorted(S_, S_+N)){
        return 0;
    }
    int l=0,r=M;
    vector<pair<int,int>> a, b;
    while(r-l>1){
        int m=(r+l)/2;
        if(can(m,N,S_,X,Y,b)){
            r=m;
            a=b;
        }else l=m;
    }
    for(int i=0;i<(int)a.size();i++){
        P[i]=a[i].first;
        Q[i]=a[i].second;
    }
    return (int)a.size();
}

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