oj.uz

Submission #16665

# Submission time Handle Problem Language Result Execution time Memory
16665 2015-09-04T03:22:01 Z suhgyuho_william Sorting (IOI15_sorting) C++
0 / 100
 3 ms 512 KB 
#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[i];
        tmp = last[i];
        last[i] = i;
        last[tested[i]] = tmp;
        swap(tested[i],tested[last[i]]);

        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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Incorrect 2 ms 384 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Incorrect 2 ms 384 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Incorrect 2 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Incorrect 2 ms 384 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -