Submission #1169809

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169809		anmattroi	Sorting (IOI15_sorting)	C++17	100 / 100	322 ms	20860 KiB

sorting

#include "sorting.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define maxn 200005
using namespace std;
using ii = pair<int, int>;


int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    int ANS;

    if (1) {
        vector<int> a(N, 0), par(N, 0); int slt;

        function<int(int)> find_set = [&](int v) {
            return par[v] < 0 ? v : par[v] = find_set(par[v]);
        };

        function<void(int, int)> union_set = [&](int u, int v) {
            u = find_set(u); v = find_set(v);
            if (u == v) return;
            if (par[u] < par[v]) swap(u, v);
            par[v] += par[u];
            par[u] = v;
            --slt;
        };

        function<int(int)> ok = [&](int o) {
            slt = N;
            for (int i = 0; i < N; i++) a[i] = i;
            for (int i = o-1; i >= 0; i--)
                swap(a[X[i]], a[Y[i]]);
            fill(par.begin(), par.end(), -1);

            for (int i = 0; i < N; i++) union_set(S[i], a[i]);

            return (N - slt <= o);
        };
        int lo = -1, hi = M;
        while (hi - lo > 1) {
            int mid = (lo + hi) >> 1;
            if (ok(mid)) hi = mid;
            else lo = mid;
        }
        ANS = hi;
    }

    vector<int> a(N, 0), pos(N, 0);

    for (int i = 0; i < N; i++) a[i] = i;
    for (int i = ANS-1; i >= 0; i--)
        swap(a[X[i]], a[Y[i]]);

    set<ii> q;


    for (int i = 0; i < N; i++)
        if (a[i] != S[i])
            q.insert(ii{a[i], S[i]});

    for (int i = 0; i < N; i++) pos[a[i]] = i;

    for (int step = 0; step < ANS; step++) {
        swap(pos[a[X[step]]], pos[a[Y[step]]]);
        swap(a[X[step]], a[Y[step]]);
        if (q.empty()) {
            P[step] = 0; Q[step] = 0;
            continue;
        }
        auto [u, v] = *q.begin();
        auto [x, y] = *q.lower_bound(ii{v, 0});
        q.erase(ii{u, v}); q.erase(ii{x, y});

        if (u != y) q.insert(ii{u, y});

        P[step] = pos[u]; Q[step] = pos[x];
    }
    return ANS;
}

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