Submission #917115

#	Time	Username	Problem	Language	Result	Execution time	Memory
917115		azosi	Sorting (IOI15_sorting)	C++17	Compilation error	0 ms	0 KiB

sorting

#include <bits/stdc++.h>

using namespace std;

int A[200001];
int B[200001], chk[200001];
pair<int, int> qry[600003];
int n, m;

bool f(int k) {
    for (int i = 0; i < n; ++i) B[i] = A[i];
    memset(chk, 0, sizeof(chk));
    for (int i = 0; i < k; ++i) swap(B[qry[i].first], B[qry[i].second]);

    int ret = 0;
    for (int i = 0; i < n; ++i) {
        if (!chk[i]) {
            int cnt = 1;
            chk[i] = 1;
            int here = i;
            while (!chk[B[here]]) {
                here = B[here];
                chk[here] = 1;
                cnt++;
            }
            ret += cnt - 1;
        }
    }
    return ret <= k;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n;
    for (int i = 0; i < n; ++i) cin >> A[i];

    cin >> m;
    for (int i = 0; i < m; ++i) cin >> qry[i].first >> qry[i].second;


    int l = 0, r = m;
    int round = -1;
    while (l <= r) {
        int mid = l + r >> 1;
        if (f(mid)) {
            round = mid;
            r = mid - 1;
        } else l = mid + 1;
    }

    cout << round << '\n';
    memset(chk, 0, sizeof(chk));
    for (int i = 0; i < round; ++i) {
        swap(A[qry[i].first], A[qry[i].second]);
    }
    vector<pair<int, int>> ans;
    for (int i = 0; i < n; ++i) {
        if (!chk[i]) {
            chk[i] = 1;
            vector<int> cycle;
            int here = i;
            cycle.push_back(here);
            while (!chk[A[here]]) {
                here = A[here];
                cycle.push_back(here);
                chk[here] = 1;
            }
            if (cycle.size() >= 2) {
                for (int j = 1; j < cycle.size(); ++j) {
                    ans.push_back({cycle[0], cycle[j]});
                    swap(A[cycle[0]], A[cycle[j]]);
                }
            }
        }
    }
    for (auto [a, b]: ans) {
        cout << a << " " << b << '\n';
    }
    if (round > ans.size()) {
        cout << 0 << " " << 0 << '\n';
    }

    for (int i = 0; i < n; ++i) {
        assert(A[i] == i);
    }

}

Compilation message (stderr)

sorting.cpp: In function 'int main()':
sorting.cpp:47:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |         int mid = l + r >> 1;
      |                   ~~^~~
sorting.cpp:72:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |                 for (int j = 1; j < cycle.size(); ++j) {
      |                                 ~~^~~~~~~~~~~~~~
sorting.cpp:82:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |     if (round > ans.size()) {
      |         ~~~~~~^~~~~~~~~~~~
/usr/bin/ld: /tmp/ccZ6gwna.o: in function `main':
grader.c:(.text.startup+0x0): multiple definition of `main'; /tmp/ccpzUPBa.o:sorting.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccZ6gwna.o: in function `main':
grader.c:(.text.startup+0x4eb): undefined reference to `findSwapPairs(int, int*, int, int*, int*, int*, int*)'
collect2: error: ld returned 1 exit status