Submission #1195192

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195192		nikulid	Sorting (IOI15_sorting)	C++20	16 / 100	4 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 next, first;
    bool already_sorted;
    vector<int> ns(N);
    for(int i=0; i<N; i++){
        ns[i] = S[i];
    }

    for(int c=0, i; true; c++){
//        cout<<"\t";
        //for(auto e:ns){
//            cout<<e<<", ";
        //}cout<<"\n";
        if(c>=N){i=N-1;}
        else{i=c;}
//        cout<<"i: "<<i<<"\n";
//        cout<<"c: "<<c<<"\n";
        for(int j=0; j<N; j++){
//            cout<<"j: "<<j<<"\n";
            if(j>0){
                if(ns[j-1] > ns[j]){
                    already_sorted=false;
                }
            }
        }
        if(already_sorted){
            return c;
        }
        // Jerry swap or whatever it's called
        swap(ns[0], ns[1]);
//        cout<<"successful jerry swap!\n";
        //for(auto x:ns){cout<<x<<" ";}
//            cout<<"\n";
//        cout<<"i: "<<i<<"\n";
        for(int j=0; j<N; j++){
            if(ns[j] == i){
                next = j;
            }
        }
//        cout<<"next: "<<next<<"\n";
//        cout<<"L37\n";
        already_sorted=true;
//        cout<<"L41\n";
        first = ((i==1)?0:i);
        P[i] = first;
        Q[i] = next;
//        cout<<"first: "<<first<<", next: "<<next<<"\n";
        swap(ns[first], ns[next]);
//        cout<<"L47\n";
        // we have "swapped" positions `i` and `trans[i]`. whatever that means.
    }

    /*for(auto x:ns){
//        cout<<x<<" ";
    //}cout<<"\n\n";*/
    return N;
}

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