Submission #1089432

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089432		ZyadH1	Xor Sort (eJOI20_xorsort)	C++17	0 / 100	0 ms	348 KiB

xorsort

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
const int mxn = 501;

int n, s;
int A[300];
vector<pair<int, int>> ans; // Simplified to pair instead of array

inline void swp(int a, int b) {
    if (a > b) {
        for (int i = a; i > b; --i) {
            ans.push_back({i, i - 1});
            ans.push_back({i - 1, i});
            ans.push_back({i, i - 1});
            swap(A[i], A[i - 1]);
        }
    } else {
        for (int i = a; i < b; ++i) {
            ans.push_back({i, i + 1});
            ans.push_back({i + 1, i});
            ans.push_back({i, i + 1});
            swap(A[i], A[i + 1]);
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> s;
    vector<int> b(n);
    for (int i = 0; i < n; ++i) {
        cin >> A[i];
        b[i] = A[i];
    }

    sort(b.begin(), b.end());
    unordered_map<int, int> mp;
    for (int i = 0; i < n; ++i) {
        mp[b[i]] = i;
    }

    for (int i = n - 1; i >= 0; --i) {
        if (i != mp[A[i]]) {
            swp(i, mp[A[i]]);
            ++i; // Continue from the next index after a swap
        }
    }

    for (const auto& p : ans) {
        cout << p.first + 1 << " " << p.second + 1 << endl;
    }
    cout << ans.size() << endl;

    return 0;
}

• Subtask 1: 0 / 25
• Subtask 2: 0 / 35
• Subtask 3: 0 / 40