Submission #640380

#	Time	Username	Problem	Language	Result	Execution time	Memory
640380		piOOE	Sorting (IOI15_sorting)	C++17	100 / 100	438 ms	15080 KiB

sorting

#include <bits/stdc++.h>
#include "sorting.h"

using namespace std;

vector<int> inv(vector<int> p) {
    vector<int> inv(p.size());
    for (int i = 0; i < p.size(); ++i) {
        inv[p[i]] = i;
    }
    return inv;
}

int findSwapPairs(int n, int p_[], int M, int X[], int Y[], int P[], int Q[]) {
    auto solve = [&](int m) {
        auto calc = [&](vector<int> p) {
            for (int i = 0; i < m; ++i) {
                swap(p[X[i]], p[Y[i]]);
            }
            return p;
        };
        vector<int> p(p_, p_ + n);
        vector<int> e = calc(p);
        vector<int> rev = inv(p), rev_e = inv(e);
        auto doSwap = [&](int i, int j, bool wtf = true) {
            int x = p[i], y = p[j];
            swap(p[i], p[j]);
            rev[y] = i, rev[x] = j;
            if (wtf) {
                int px = rev_e[x], py = rev_e[y];
                swap(e[px], e[py]);
                rev_e[e[px]] = px, rev_e[e[py]] = py;
            }
        };
        int i = 0;
        for (int r = 0; r < m; ++r){
            doSwap(X[r], Y[r], 0);
            P[r] = 0, Q[r] = 0;
            for (; i < n; ++i) {
                if (e[i] != i) {
                    P[r] = rev[i];
                    Q[r] = rev[e[i]];
                    break;
                }
            }
            doSwap(P[r], Q[r]);
        }
        return is_sorted(p.begin(), p.end());
    };
    int low = -1, high = M;
    while (low + 1 < high) {
        int m = (low + high) >> 1;
        if (solve(m)) {
            high = m;
        } else {
            low = m;
        }
    }
    solve(high);
    return high;
}

Compilation message (stderr)

sorting.cpp: In function 'std::vector<int> inv(std::vector<int>)':
sorting.cpp:8:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 |     for (int i = 0; i < p.size(); ++i) {
      |                     ~~^~~~~~~~~~

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