Submission #726596

#	Time	Username	Problem	Language	Result	Execution time	Memory
726596		becaido	Sorting (IOI15_sorting)	C++17	100 / 100	155 ms	10700 KiB

sorting

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;

#ifndef WAIMAI
#include "sorting.h"
#endif

const int N = 2e5 + 5;

int n;
int a[N];
bool vs[N];

bool ok(int r, int S[], int X[], int Y[]) {
    for (int i = 0; i < n; i++) a[i] = S[i], vs[i] = 0;
    for (int i = 0; i < r; i++) swap(a[X[i]], a[Y[i]]);
    int cnt = n;
    for (int i = 0; i < n; i++) if (!vs[i]) {
        cnt--;
        for (int cur = i; !vs[cur]; cur = a[cur]) vs[cur] = 1;
    }
    return cnt <= r;
}

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    n = N;
    int l = 0, r = M;
    while (l < r) {
        int mid = (l + r) / 2;
        if (ok(mid, S, X, Y)) r = mid;
        else l = mid + 1;
    }
    for (int i = 0; i < n; i++) a[i] = S[i], vs[i] = 0;
    for (int i = 0; i < r; i++) swap(a[X[i]], a[Y[i]]);
    int sz = 0;
    for (int i = 0; i < n; i++) if (!vs[i]) {
        int last = -1, cur = i;
        while (!vs[cur]) {
            vs[cur] = 1;
            if (last != -1) P[sz] = last, Q[sz] = cur, sz++;
            last = cur;
            cur = a[cur];
        }
    }
    while (sz < r) P[sz] = Q[sz] = 0, sz++;
    for (int i = 0; i < n; i++) a[S[i]] = i;
    for (int i = 0; i < r; i++) {
        swap(a[S[X[i]]], a[S[Y[i]]]);
        swap(S[X[i]], S[Y[i]]);
        P[i] = a[P[i]], Q[i] = a[Q[i]];
        swap(a[S[P[i]]], a[S[Q[i]]]);
        swap(S[P[i]], S[Q[i]]);
    }
    return r;
}

Compilation message (stderr)

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:27:23: warning: declaration of 'N' shadows a global declaration [-Wshadow]
   27 | int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
      |                   ~~~~^
sorting.cpp:10:11: note: shadowed declaration is here
   10 | const int N = 2e5 + 5;
      |           ^

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