Submission #753719

#	Time	Username	Problem	Language	Result	Execution time	Memory
753719		nicksms	Sorting (IOI15_sorting)	C++17	100 / 100	159 ms	24944 KiB

sorting

/**
 *      Author:  Nicholas Winschel
 *      Created: 05.09.2023 19:37:58
**/

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using db=long double;
template<class T> using V=vector<T>;
using vi = V<int>;
using vl = V<ll>;
using pi = pair<int,int>;
#define f first
#define s second
#define sz(x) (int)((x).size())

#include "sorting.h"

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    auto tr = [&](int l) -> bool {
        // cout << l << endl;
        vi s(N);
        for (int i = 0; i < N; i++) {
            s[i]=S[i];
        }
        for (int i = 0; i < l; i++) {
            swap(s[X[i]],s[Y[i]]);
        }
        // for (int i = 0; i < N; i++) {
        //     cout << s[i] << " ";
        // }
        // cout << "\n";
        V<bool> vis(N);
        int cnt = 0;
        auto dfs = [&](int v, auto &&dfs) -> void {
            if (vis[v]) return;
            vis[v]=true;
            dfs(s[v], dfs);
        };
        for (int i = 0; i < N; i++) {
            if (!vis[i]) {
                cnt++;
                dfs(i,dfs);
            }
        }
        cnt = N-cnt;
        return cnt <= l;
    };
    int l = -1, r = M;
    while (r-l > 1) {
        int m = (l+r)/2;
        if (tr(m)) r=m;
        else l=m;
    }
    vi s(N);
    for (int i = 0; i < N; i++) {
        s[i]=S[i];
    }
    for (int i = 0; i < r; i++) {
        swap(s[X[i]],s[Y[i]]);
    }
    V<pi> pans;
    V<bool> vis(N);
    vi stk;
    auto dfs = [&](int v, auto &&dfs) -> void {
        if (vis[v]) return;
        vis[v]=true;
        dfs(s[v], dfs);
        stk.push_back(v);
    };
    for (int i = 0; i < N; i++) {
        if (!vis[i]) {
            stk = vi();
            dfs(i,dfs);
            for (int j = 0; j < sz(stk)-1; j++) {
                pans.emplace_back(stk[j], stk[j+1]);
                // cout << stk[j] << " " << stk[j+1] << endl;
            }
        }
    }
    while (sz(pans) < r) pans.emplace_back(0,0);
    vi cur(N); iota(cur.begin(), cur.end(), 0);
    vi rcur=cur;
    for (int i = r-1; i >= 0; i--) {
        pi h = pans[i];
        P[i] = rcur[h.f];
        Q[i] = rcur[h.s];
        swap(cur[X[i]], cur[Y[i]]);
        rcur[cur[X[i]]]=X[i];
        rcur[cur[Y[i]]]=Y[i];
    }
    return r;
}

Compilation message (stderr)

sorting.cpp: In lambda function:
sorting.cpp:36:38: warning: declaration of 'dfs' shadows a previous local [-Wshadow]
   36 |         auto dfs = [&](int v, auto &&dfs) -> void {
      |                               ~~~~~~~^~~
sorting.cpp:36:14: note: shadowed declaration is here
   36 |         auto dfs = [&](int v, auto &&dfs) -> void {
      |              ^~~
sorting.cpp: In lambda function:
sorting.cpp:66:34: warning: declaration of 'dfs' shadows a previous local [-Wshadow]
   66 |     auto dfs = [&](int v, auto &&dfs) -> void {
      |                           ~~~~~~~^~~
sorting.cpp:66:10: note: shadowed declaration is here
   66 |     auto dfs = [&](int v, auto &&dfs) -> void {
      |          ^~~

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