Submission #16668

#	Time	Username	Problem	Language	Result	Execution time	Memory
16668		suhgyuho_william	Sorting (IOI15_sorting)	C++98	100 / 100	722 ms	17784 KiB

sorting

#include "sorting.h"
#include <algorithm>
using namespace std;

int n,R;
int a[200002];
int x[600002],y[600002];
int p[600002],q[600002];
int tested[200002],tester[200002];
int last[200002],where[200002];

bool sorting(){
    int i,cnt;
    int tmp;

    cnt = -1;
    for(i=0; i<n; i++) tested[i] = a[i];
    for(i=0; i<n; i++) tester[i] = a[i];
    for(i=0; i<n; i++) where[tester[i]] = i;
    for(i=0; i<R; i++){
        swap(tested[x[i]],tested[y[i]]);
    }
    for(i=0; i<n; i++) last[tested[i]] = i;

    for(i=0; i<n; i++){
        if(last[i] == i) continue;

        cnt++;
        if(cnt >= R) return false;

        where[tester[x[cnt]]] = y[cnt];
        where[tester[y[cnt]]] = x[cnt];
        swap(tester[x[cnt]],tester[y[cnt]]);

        p[cnt] = where[tested[i]];
        q[cnt] = where[tested[last[i]]];
        //if(p[cnt] > q[cnt]) swap(p[cnt],q[cnt]);
        tmp = last[i];
        last[tested[i]] = last[i];
        last[i] = i;
        swap(tested[i],tested[tmp]);

        where[tester[p[cnt]]] = q[cnt];
        where[tester[q[cnt]]] = p[cnt];
        swap(tester[p[cnt]],tester[q[cnt]]);
    }
    for(i=cnt+1; i<R; i++) p[i] = q[i] = 0;

    return true;
}

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    int i,s,e;

    s = 0;
    e = M;
    n = N;
    for(i=0; i<N; i++){
        a[i] = S[i];
        x[i] = X[i];
        y[i] = Y[i];
    }
    while(s != e){
        R = (s+e)/2;
        if(sorting()) e = R;
        else s = R+1;
    }
    R = (s+e)/2;

    sorting();
    for(i=0; i<R; i++){
        P[i] = p[i];
        Q[i] = q[i];
    }

	return R;
}

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