Submission #1226046

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226046		cpdreamer	Sorting (IOI15_sorting)	C++20	16 / 100	4 ms	328 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;
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 p[n];
    int a[n];
    for (int i=0;i<n;i++) {
        a[i]=S[i];
    }
    for (int i=0;i<m;i++) {
        swap(a[X[i]],a[Y[i]]);
    }
    for (int i=0;i<n;i++) {
        p[a[i]]=i;
    }
    swap(S[X[0]],S[Y[0]]);
    int c=0;
    for (int i=0;i<n;i++) {
        int id1=-1;
        for (int j=0;j<n;j++) {
            if (S[j]==i) {
                id1=j;
            }
        }
        int id2=-1;
        for (int j=0;j<n;j++) {
            if (p[S[j]]==i) {
                id2=j;
            }
        }
        swap(p[i],p[S[id2]]);
        P[i]=id1,Q[i]=id2;
        swap(S[P[i]],S[Q[i]]);
        if (i<n-1) {
            swap(S[X[i+1]],S[Y[i+1]]);
        }
    }
    for (int i=n;i<m;i++) {
        P[i]=0,Q[i]=0;
    }
    return m;
}

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