Submission #1212348

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212348		XCAC197	Sorting (IOI15_sorting)	C++20	16 / 100	6 ms	332 KiB

sorting

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

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    
    int A [N];
    for(int i = 0; i < N; i++){
        A[i] = i;
    }
    //go backwards
    for(int i = M-1; i >= 0; i--){
        swap(A[X[i]], A[Y[i]]);
    }
    for(int i = 0; i < M; i++){
        swap(A[X[i]], A[Y[i]]);
        swap(S[X[i]], S[Y[i]]);
        bool done = false;
        for(int j = 0; j < N; j++){
            if(S[j] != A[j]){
                int kva = 0;
                for(int k = 0; k < N; k++){
                    if(S[k] == A[j]){
                        kva = k;
                    }
                }
                swap(S[j], S[kva]);
                P[i] = j;
                Q[i] = kva;
                done = true;
                break;
            }
        }
        if(!done){
            P[i] = 0;
            Q[i] = 0;
        }
    }
    for(int i = 0; i < N; i++){
        assert(A[i] == i);
    }
    /*for(int i = 0; i < N; i++){
        cerr << A[i] << " ";
    }
    cerr << endl;
    for(int i = 0; i < N; i++){
        cerr << S[i] << " ";
    }
    cerr << endl;*/
    return M;
}

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