Submission #71482

#	Time	Username	Problem	Language	Result	Execution time	Memory
71482		RezwanArefin01	Sorting (IOI15_sorting)	C++17	0 / 100	4 ms	384 KiB

sorting

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

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

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    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) {
                P[cnt] = i; 
                Q[cnt++] = pos[i]; 
                int x = p[i]; 
                swap(p[i], p[pos[i]]); 
                pos[x] = pos[i];
            }
        }
        return cnt <= 1 + t; 
    };
    int lo = 0, hi = M, ans = -1;
    while(lo <= hi) {
        int mid = lo + hi >> 1; 
        if(check(mid)) ans = mid, hi = mid - 1; 
        else lo = mid + 1; 
    }
    check(ans); 
    return 1 + ans; 
}

Compilation message (stderr)

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:8: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:30:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid = lo + hi >> 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