Submission #292874

#	Time	Username	Problem	Language	Result	Execution time	Memory
292874		alexandra_udristoiu	Sorting (IOI15_sorting)	C++14	100 / 100	338 ms	25720 KiB

sorting

#include "sorting.h"
#include<algorithm>
#define DIM 200005
#define f first
#define s second
using namespace std;
static int n, m, v[DIM], p[DIM], ind[DIM], viz[DIM], pos[DIM];
static pair<int, int> sol[DIM], w[DIM];
static void swappos(int x, int y){
    swap(p[x], p[y]);
    pos[ p[x] ] = x;
    pos[ p[y] ] = y;
}
static int solve(int k){
    int i, nr = 0, x;
    for(i = 1; i <= n; i++){
        ind[i] = i;
        viz[i] = 0;
    }
    for(i = 1; i <= k; i++){
        swap(ind[ w[i].f ], ind[ w[i].s ]);
    }
    for(i = 1; i <= n; i++){
        p[i] = v[ ind[i] ];
    }
    for(i = 1; i <= n; i++){
        if(viz[i] == 0){
            viz[i] = 1;
            x = i;
            while(viz[ p[x] ] == 0){
                sol[++nr] = make_pair(p[x], p[ p[x] ]);
                x = p[x];
                viz[x] = 1;
            }
        }
    }
    if(nr <= k){
        for(i = 1; i <= n; i++){
            p[i] = v[i];
            pos[ p[i] ] = i;
        }
        for(i = 1; i <= nr; i++){
            swappos(w[i].f, w[i].s);
            sol[i].f = pos[ sol[i].f ];
            sol[i].s = pos[ sol[i].s ];
            swappos(sol[i].f, sol[i].s);
        }
        for(; i <= k; i++){
            sol[i] = make_pair(1, 1);
        }
        return 1;
    }
    return 0;
}

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    int i, st, dr, mid;
    n = N;
    m = M;
    for(i = 1; i <= n; i++){
        v[i] = S[i - 1] + 1;
    }
    for(i = 1; i <= m; i++){
        w[i] = make_pair(X[i - 1] + 1, Y[i - 1] + 1);
    }
    st = 0;
    dr = m;
    while(st <= dr){
        mid = (st + dr) / 2;
        if( solve(mid) ){
            dr = mid - 1;
        }
        else{
            st = mid + 1;
        }
    }
    solve(st);
    for(i = 0; i < st; i++){
        P[i] = sol[i + 1].f - 1;
        Q[i] = sol[i + 1].s - 1;
    }
    return st;
}

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