Submission #134467

#	Time	Username	Problem	Language	Result	Execution time	Memory
134467		evpipis	Sorting (IOI15_sorting)	C++11	100 / 100	285 ms	26776 KiB

sorting

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

#define fi first
#define se second
#define pb push_back
#define mp make_pair
typedef pair<int, int> ii;

const int len = 6e5+5;
int fin[len], arr[len], vis[len], plate[len], pos[len];
int n, m;
ii mov[len];

bool check(int x){
    for (int i = 0; i < n; i++)
        fin[i] = i;
    for (int i = 0; i < x; i++)
        swap(fin[mov[i].fi], fin[mov[i].se]);

    for (int i = 0; i < n; i++)
        plate[i] = fin[arr[i]], vis[i] = 0;

    int rem = n;
    for (int i = 0; i < n; i++){
        if (vis[i]) continue;

        int cur = plate[i];
        vis[i] = 1;
        while (cur != i)
            vis[cur] = 1, cur = plate[cur];

        rem--;
    }

    return (rem <= x);
}

int bs(){
    int l = 0, r = m, ans;
    while (l <= r){
        int mid = (l+r)/2;
        if (check(mid))
            ans = mid, r = mid-1;
        else
            l = mid+1;
    }

    return ans;
}

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    //freopen("CON", "w", stdin);
    //printf("hello\n");
    n = N, m = M;
    for (int i = 0; i < n; i++)
        arr[i] = S[i];
    for (int i = 0; i < m; i++)
        mov[i] = mp(X[i], Y[i]);

    int k = bs();
    check(k);

    //printf("k = %d\n", k);

    for (int i = 0; i < n; i++)
        fin[i] = i, pos[i] = i;

    /*for (int i = 0; i < n; i++)
        printf("%d ", pos[i]);
    printf("\n");*/

    for (int i = 0, j = 0; i < k; i++){
        //printf("i = %d\n", i);
        int a = mov[i].fi, b = mov[i].se;
        //printf("a = %d, b = %d\n", a, b);
        swap(pos[fin[a]], pos[fin[b]]);
        swap(fin[a], fin[b]);

        /*for (int x = 0; x < n; x++)
            printf("%d ", pos[x]);
        printf("\n");*/

        while (j < n && plate[j] == j)
            j++;

        if (j < n){
            a = j, b = plate[j];
            P[i] = pos[a];
            Q[i] = pos[b];
            plate[a] = plate[b];
            plate[b] = b;
        }
        else{
            P[i] = 0;
        Q[i] = 0;
        }
    }

    /*for (int i = 0; i < k; i++){
        int a = mov[i].fi, b = mov[i].se;
        swap(arr[a], arr[b]);

        a = P[i], b = Q[i];
        swap(arr[a], arr[b]);

        for (int j = 0; j < n; j++)
            printf("%d ", arr[j]);
        printf("\n");
    }*/

    return k;
}

Compilation message (stderr)

sorting.cpp: In function 'int bs()':
sorting.cpp:50:12: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
     return ans;
            ^~~

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