Submission #307490

#	Time	Username	Problem	Language	Result	Execution time	Memory
307490		lohacho	Sorting (IOI15_sorting)	C++14	100 / 100	490 ms	22784 KiB

sorting

#include "sorting.h"
#include <bits/stdc++.h>

using namespace std;

using LL = long long;
const int INF = (int)1e9 + 7;
const int NS = (int)2e5 + 4;
int mov[NS], Index[NS], pos[NS], S_save[NS], ba[NS];

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    for(int i = 0; i < N; ++i){
        S_save[i] = S[i];
    }
    int low = 0, high = N - 1, mid;
    function < int() > can_sort = [&](){
        for(int i = 0; i < N; ++i){
            S[i] = S_save[i];
            mov[i] = i; Index[S[i]] = i; ba[i] = S[i];
            pos[S[i]] = i;
        }
        for(int i = mid - 1; i >= 0; --i){
            swap(mov[X[i]], mov[Y[i]]);
        }
        int diff = 0;
        for(int i = 0; i < mid; ++i){
            while(diff < N && mov[diff] == S[diff]) ++diff;
            swap(Index[ba[X[i]]], Index[ba[Y[i]]]);
            swap(ba[X[i]], ba[Y[i]]);
            if(diff >= N){
                P[i] = Q[i] = 0;
            }
            else{
                P[i] = Index[S[diff]], Q[i] = Index[mov[diff]];
                swap(Index[S[diff]], Index[mov[diff]]);
                swap(ba[P[i]], ba[Q[i]]);
                swap(S[diff], S[pos[mov[diff]]]);
                swap(pos[S[diff]], pos[S[pos[mov[diff]]]]);
            }
        }
        while(diff < N && mov[diff] == S[diff]) ++diff;
        if(diff >= N) return 1;
        else return 0;
    };
    while(low < high){
        mid = (low + high) >> 1;
        for(int i = 0; i < N; ++i) P[i] = Q[i] = 0;
        if(can_sort()){
            high = mid;
        }
        else{
            low = mid + 1;
        }
    }
    mid = low;
    can_sort();
    return low;
}

Compilation message (stderr)

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:11:39: warning: unused parameter 'M' [-Wunused-parameter]
   11 | int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
      |                                   ~~~~^

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