Submission #114134

#	Time	Username	Problem	Language	Result	Execution time	Memory
114134		nvmdava	Sorting (IOI15_sorting)	C++17	0 / 100	1050 ms	2468 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]]);
        }
    }
    cerr<<r<<'\n';
    for(int i = 0; i < r; i++){
        swap(val[X[i]], val[Y[i]]);
        swap(loc[val[X[i]]], loc[val[Y[i]]]);
        for(int i = 0; i < n; i++) cerr<<val[i]<<' ';
        cerr<<'\n';
        if(sw.empty()){
            P[i] = 0;
            Q[i] = 0;
        } else {
            cerr<<"SWAP: "<<sw.back().ff<<' '<<sw.back().ss<<'\n';
            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();
        }
        for(int i = 0; i < n; i++) cerr<<val[i]<<' ';
        cerr<<'\n';
    }


    return l;
}

Compilation message (stderr)

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:63:17: warning: declaration of 'i' shadows a previous local [-Wshadow]
         for(int i = 0; i < n; i++) cerr<<val[i]<<' ';
                 ^
sorting.cpp:60:13: note: shadowed declaration is here
     for(int i = 0; i < r; i++){
             ^
sorting.cpp:76:17: warning: declaration of 'i' shadows a previous local [-Wshadow]
         for(int i = 0; i < n; i++) cerr<<val[i]<<' ';
                 ^
sorting.cpp:60:13: note: shadowed declaration is here
     for(int i = 0; i < r; i++){
             ^
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: 0 / 8
• Subtask 2: 0 / 12
• Subtask 3: 0 / 16
• Subtask 4: 0 / 18
• Subtask 5: 0 / 20
• Subtask 6: 0 / 26