Submission #117855

#	Time	Username	Problem	Language	Result	Execution time	Memory
117855		zubec	Sorting (IOI15_sorting)	C++14	74 / 100	73 ms	24100 KiB

sorting

#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;

const int N = 200100;

int n, a[N], pos[N];

pair<int, int> pr[N];
pair<int, int> anss[N];

int b[N];

int f(int m){
    for (int i = 0; i < n; i++)
        b[i] = a[i];
    for (int i = 1; i <= m; i++){
        swap(b[pr[i].first], b[pr[i].second]);
    }
    for (int i = 0; i < n; i++){
        pos[b[i]] = i;
    }
    int ans = 0;
    for (int i = 0; i < n; i++){
        if (b[i] != i){
            anss[ans] = {i, b[i]};
            ++ans;
            int ps = b[i];
            swap(b[i], b[pos[i]]);
            swap(pos[ps], pos[i]);
        }
    }
    if (ans > m)
        return -1;
    while(ans < m){
        anss[ans] = {0, 0};
        ++ans;
    }
    return ans;
}

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {

    n = N;
    for (int i = 0; i < n; i++)
        a[i] = S[i];
    for (int i = 0; i < M; i++){
        pr[i+1] = {X[i], Y[i]};
    }
    int l = 0, r = M;
    while(l < r){
        int mid = (l+r)>>1;
        if (f(mid) != -1)
            r = mid; else
            l = mid+1;
    }
    f(l);
    for (int i = 0; i < n; i++)
        pos[S[i]] = i;
    for (int i = 0; i < l; i++){
        swap(pos[S[X[i]]], pos[S[Y[i]]]);
        swap(S[X[i]], S[Y[i]]);
        int a = anss[i].first;
        int b = anss[i].second;
        P[i] = pos[a];
        Q[i] = pos[b];
        swap(S[pos[a]], S[pos[b]]);
        swap(pos[a], pos[b]);
    }

    return l;

}

/**

5
3 0 4 2 1
5
1 1
4 0
2 3
1 4
0 4


*/

Compilation message (stderr)

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:42:76: warning: declaration of 'N' shadows a global declaration [-Wshadow]
 int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
                                                                            ^
sorting.cpp:5:11: note: shadowed declaration is here
 const int N = 200100;
           ^
sorting.cpp:63:13: warning: declaration of 'a' shadows a global declaration [-Wshadow]
         int a = anss[i].first;
             ^
sorting.cpp:7:8: note: shadowed declaration is here
 int n, a[N], pos[N];
        ^
sorting.cpp:64:13: warning: declaration of 'b' shadows a global declaration [-Wshadow]
         int b = anss[i].second;
             ^
sorting.cpp:12:5: note: shadowed declaration is here
 int b[N];
     ^

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