Submission #1122113

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122113		SalihSahin	Sorting (IOI15_sorting)	C++14	0 / 100	100 ms	596 KiB

sorting

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
#include "sorting.h"

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]){
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    bool sorted = 1;
    for(int i = 0; i < N; i++){
        if(S[i] != i) sorted = 0;
    }
    if(sorted) return 0;

    int ans = 0;
    for(int i = 0; i < M; i++){
        ans++;
        swap(S[X[i]], S[Y[i]]);
        sorted = 1;
        for(int j = 0; j < N; j++){
            if(S[j] != j) sorted = 0;
        }
        if(sorted){
            P[i] = Q[i] = 0;
            return ans;
        }

        int ind1 = 0;
        for(int j = 2; j < N; j++){
            if(S[j] != j){
                ind1 = j;
                break;
            }
        }

        vector<int> perm(N);
        for(int j = 0; j < N; j++){
            perm[j] = j;
        }
        shuffle(perm.begin(), perm.end(), rng);

        int ind2 = -1;
        for(int j = 0; j < N; j++){
            if(perm[j] == ind1) continue;
            if(S[perm[j]] != perm[j] && S[ind1] == perm[j]){
                ind2 = perm[j];
            }
        }

        if(ind2 == 0){
            P[i] = 0;
            Q[i] = 0;
            continue;
        }

        swap(S[ind1], S[ind2]);
        P[i] = ind1;
        Q[i] = ind2;

        sorted = 1;
        for(int j = 0; j < N; j++){
            if(S[j] != j) sorted = 0;
        }
        if(sorted){
            return ans;
        }
    }

    return -1;
}

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