Submission #1226130

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226130		cpdreamer	Sorting (IOI15_sorting)	C++20	100 / 100	163 ms	14708 KiB

sorting

#include "sorting.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
const long long INF = 1e17;
typedef long long ll;
const ll MOD = 1000002022;
#define F first
#define pb push_back
#define V vector
#define all(v) v.begin(), v.end()
typedef tree<int,null_type,less<int>,rb_tree_tag, tree_order_statistics_node_update> indexed_multiset;
bool check(int m,int n,int S[],int X[],int Y[],int P[],int Q[]) {
    int id[n];
    int p[n];
    int a[n];
    int b[n];
    for (int i=0;i<n;i++) {
        a[i]=S[i];
        id[S[i]]=i;
    }
    for (int i=0;i<m;i++) {
        swap(a[X[i]],a[Y[i]]);
    }
    for (int i=0;i<n;i++) {
        p[i]=a[i];
        b[a[i]]=i;
    }
    int c=0;
    swap(id[S[X[0]]],id[S[Y[0]]]);
    swap(S[X[0]],S[Y[0]]);
    for (int i=0;i<n;i++) {
        if (c==m)break;
        int num1=i;
        int num2=a[i];
        if (num1==num2)continue;
        swap(b[num1],b[num2]);
        a[b[num1]]=num1;
        a[b[num2]]=num2;
        P[c]=id[num1],Q[c]=id[num2];
        if (c+1<m) {
            swap(id[S[P[c]]],id[S[Q[c]]]);
            swap(S[P[c]],S[Q[c]]);
            swap(id[S[X[c+1]]],id[S[Y[c+1]]]);
            swap(S[X[c+1]],S[Y[c+1]]);
        }
        c++;
    }
    for (int i=c;i<m;i++) {
        P[i]=0,Q[i]=0;
    }
    for (int i=0;i<n;i++) {
        if (a[i]!=i) {
            return false;
        }
    }
    return true;
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {

    P[0] = 0;
    Q[0] = 0;
    int n=N,m=M;
    int l=0,r=m;
    int ans=-1;
    while (l<=r) {
        int mid=l+(r-l)/2;
        int c[n];
        for (int i=0;i<n;i++) {
            c[i]=S[i];
        }
        if (check(mid,n,c,X,Y,P,Q)) {
            ans=mid;
            r=mid-1;
        }
        else
            l=mid+1;
    }
    int c[n];
    for (int i=0;i<n;i++) {
        c[i]=S[i];
    }
    check(ans,n,c,X,Y,P,Q);
    return ans;
}

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