Submission #114138

#	Time	Username	Problem	Language	Result	Execution time	Memory
114138		nvmdava	Sorting (IOI15_sorting)	C++17	0 / 100	3 ms	768 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 n;
vector<pii> sw;

bool in[NN];

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

int findSwapPairs(int N, int qq[], int M, int X[], int Y[], int P[], int Q[]) {
    int cyc, l = 0, r = N, m, i;

    for(i = 0; i < N; i++){
        val[i] = qq[i];
        loc[val[i]] = i;
    }

    while(l != r){
        cyc = 0;
        m = (l + r) >> 1;
        for(i = 0; i < m; i++)
            swap(val[X[i]], val[Y[i]]);

        for(i = 0; i < N; i++){
            if(in[i]) continue;
            cyc++;
            dfs(i, val[i]);
        }
        if(N - cyc <= m) r = m;
        else l = m + 1;
        memset(in, 0, sizeof in);
        for(i = m - 1; i >= 0; i--)
            swap(val[X[i]], val[Y[i]]);

    }

    for(i = 0; i < r; i++)
        swap(val[X[i]], val[Y[i]]);

    for(i = 0; i < N; i++){
        while(val[i] != i){
            sw.push_back({val[i], i});
            swap(val[i], val[val[i]]);
        }
    }
    for(int i = n - 1; i >= 0; i--)
        val[loc[i]] = i;

    for(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:59:13: warning: declaration of 'i' shadows a previous local [-Wshadow]
     for(int i = n - 1; i >= 0; i--)
             ^
sorting.cpp:24:31: note: shadowed declaration is here
     int cyc, l = 0, r = N, m, i;
                               ^
sorting.cpp:23: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: 0 / 8
• Subtask 2: 0 / 12
• Subtask 3: 0 / 16
• Subtask 4: 0 / 18
• Subtask 5: 0 / 20
• Subtask 6: 0 / 26