Submission #71489

#	Time	Username	Problem	Language	Result	Execution time	Memory
71489		RezwanArefin01	Sorting (IOI15_sorting)	C++17	100 / 100	282 ms	13176 KiB

sorting

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

const int N = 2e5 + 10; 
int p[N], pos[N]; 
int tp[N], tq[N]; 

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    bool flag = 1;
    for(int i = 0; i < N - 1; i++) 
        flag &= S[i] < S[i + 1];
    if(flag) return 0; 
    auto check = [&](int t) {
        for(int i = 0; i < N; i++) p[i] = S[i]; 
        for(int i = 0; i <= t; i++) swap(p[X[i]], p[Y[i]]);
        for(int i = 0; i < N; i++) pos[p[i]] = i; 
        int cnt = 0;
        for(int i = 0; i < N; i++) {
            if(p[i] != i) {
                tp[cnt] = i;
                tq[cnt++] = p[i]; 
                int x = p[i]; 
                swap(p[i], p[pos[i]]); 
                pos[x] = pos[i];
            }
        }
        return cnt; 
    };
    int lo = 0, hi = M, ans = -1;
    while(lo <= hi) {
        int mid = lo + hi >> 1; 
        if(check(mid) <= mid + 1) ans = mid, hi = mid - 1; 
        else lo = mid + 1; 
    }
    for(int i = check(ans); i <= ans; i++) 
        tp[i] = tq[i] = 0; 
    for(int i = 0; i < N; i++) p[i] = S[i]; 
    for(int i = 0; i < N; i++) pos[p[i]] = i; 
    auto fn = [&](int i, int j) {
        pos[p[i]] = j; 
        pos[p[j]] = i; 
        swap(p[i], p[j]);
    }; 
    for(int i = 0; i <= ans; i++) {
        fn(X[i], Y[i]); 
        P[i] = pos[tp[i]]; 
        Q[i] = pos[tq[i]]; 
        fn(P[i], Q[i]); 
    }
    return 1 + ans; 
}

Compilation message (stderr)

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:9:76: warning: declaration of 'N' shadows a global declaration [-Wshadow]
 int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
                                                                            ^
sorting.cpp:5:11: note: shadowed declaration is here
 const int N = 2e5 + 10; 
           ^
sorting.cpp:32:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid = lo + hi >> 1; 
                   ~~~^~~~

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