Submission #114135

#	Time	Username	Problem	Language	Result	Execution time	Memory
114135		nvmdava	Sorting (IOI15_sorting)	C++17	100 / 100	200 ms	23028 KiB

sorting

//#include "sorting.h"
#include <bits/stdc++.h>
#define pii pair<int, int>
#define ff first
#define ss second
using namespace std;

#define NN 200005

int val[NN];
int loc[NN];
int S[NN];
int n;
vector<pii> sw;

bool in[NN];

void dfs(int s, int now){
    in[now] = 1;
    if(now == s) return;
    dfs(s, S[now]);
}

int findSwapPairs(int N, int qq[], int M, int X[], int Y[], int P[], int Q[]) {
    n = N;
    for(int i = 0; i < N; i++){
        S[i] = qq[i];
        val[i] = S[i];
        loc[val[i]] = i;
    }
    int l = 0, r = N, m;
    while(l != r){
        int cyc = 0;
        m = (l + r) >> 1;
        for(int i = 0; i < m; i++)
            swap(S[X[i]], S[Y[i]]);

        for(int i = 0; i < n; i++){
            if(in[i]) continue;
            cyc++;
            dfs(i, S[i]);
        }
        if(n - cyc <= m) r = m;
        else l = m + 1;
        memset(in, 0, sizeof in);
        for(int i = 0; i < n; i++)
            S[i] = val[i];

    }

    for(int i = 0; i < r; i++)
        swap(S[X[i]], S[Y[i]]);
    for(int i = 0; i < n; i++){
        while(S[i] != i){
            sw.push_back({S[i], i});
            swap(S[i], S[S[i]]);
        }
    }
    for(int i = 0; i < r; i++){
        swap(val[X[i]], val[Y[i]]);
        swap(loc[val[X[i]]], loc[val[Y[i]]]);
        if(sw.empty()){
            P[i] = 0;
            Q[i] = 0;
        } else {
            P[i] = loc[sw.back().ff];
            Q[i] = loc[sw.back().ss];
            swap(val[P[i]], val[Q[i]]);
            swap(loc[val[P[i]]], loc[val[Q[i]]]);
            sw.pop_back();
        }
    }


    return l;
}

Compilation message (stderr)

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:24:40: warning: unused parameter 'M' [-Wunused-parameter]
 int findSwapPairs(int N, int qq[], int M, int X[], int Y[], int P[], int Q[]) {
                                        ^

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