제출 #1195333

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1195333		nikulid	Sorting (IOI15_sorting)	C++20	20 / 100	10 ms	328 KiB

sorting

#include "sorting.h"
#include <vector>

using namespace std;

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    int n=N;
    int i;
    bool donene;
    vector<int> fns(n), cns(n);
    for(int i=0; i<n; i++){
        fns[i] = S[i];
        cns[i] = S[i];
    }


    for(int i=0; i<3*n; i++){
        swap(fns[X[i]], fns[Y[i]]);
    }
    // now we have N swaps to make until it must be sorted...
    // this is more than enough :p

    int target;

    for(int c=0; c<10*n; c++){
        i = c%n;

        if(1==1) // check to see if it's already sorted (how... goofy)
        {
            donene=true;
            for(int t=1; t<n; t++){
                if(cns[t-1] > cns[t]){
                    donene=false;
                    break;
                }
            }
            if(donene)return c;
        }


        swap(cns[X[i]], cns[Y[i]]);

        for(int _=0; _<n; _++){
            // only do swaps with respect to the final layout
            // we do not care about cns
            // cns only exists because the question is stupid
            if(fns[_]==i){
                target = _;
                break;
            }
        }
        P[i] = i;
        Q[i] = target;
        swap(fns[P[i]], fns[Q[i]]);
        swap(cns[P[i]], cns[Q[i]]);
    }

    return 3*n;
}

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