제출 #1122149

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1122149		SalihSahin	Sorting (IOI15_sorting)	C++14	0 / 100	40 ms	336 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;
        }

        if(S[0] + S[1] != 1){
            int ind1 = 0;
            for(int j = 2; j < N; j++){
                if(S[j] == 0 || S[j] == 1){
                    ind1 = j;
                    break;
                }
            }
            int ind2 = 1;
            if(S[0] > 1 || S[1] > 1) ind2 = S[ind1];
            else if(S[0] > 1) ind2 = 0;
            
            swap(S[ind1], S[ind2]);
            P[i] = ind1;
            Q[i] = ind2;
            continue;
        }

        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 || perm[j] < 2) 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