Submission #774808

#	Time	Username	Problem	Language	Result	Execution time	Memory
774808		vjudge1	Xor Sort (eJOI20_xorsort)	C++17	0 / 100	1 ms	212 KiB

xorsort

#include <bits/stdc++.h>

using namespace std;

int n, s;
vector<pair<int, int>> v;
vector<int> valueToIndex, indexToValue;
vector<pair<int, int>> operations;

void performOperation(const int& i, const int& j)
{
    operations.emplace_back(i, j);
}

void performSwap(const int& i, const int& j)
{
    assert(max(i - j, j - i) == 1);
    performOperation(i, j);
    performOperation(j, i);
    performOperation(i, j);
}

/*
 * a b
 * a^b b
 * a^b a
 *
 */

int main()
{
    // freopen("inp.txt", "r", stdin);

    ios::sync_with_stdio(false);

    cin >> n >> s;
    v.resize(n);
    for (int i = 0; i < n; i++)
    {
        cin >> v[i].first;
        v[i].second = i;
    }

    sort(v.begin(), v.end());

    valueToIndex.resize(n);
    indexToValue.resize(n);
    for (int i = 0; i < n; i++)
    {
        indexToValue[i] = v[i].second;
        valueToIndex[indexToValue[i]] = i;
    }

    for (int i = 0; i < n; i++)
    {
        int x = valueToIndex[i];
        for (int i1 = x; i1 > i; i1--)
        {
            int index = valueToIndex[i];
            int otherIndex = index - 1;
            int prevValueAtIndex = i;
            int prevValueAtOtherIndex = indexToValue[otherIndex];

            valueToIndex[prevValueAtIndex] = otherIndex;
            indexToValue[otherIndex] = prevValueAtIndex;

            valueToIndex[prevValueAtOtherIndex] = index;
            indexToValue[index] = prevValueAtOtherIndex;

            performSwap(index, otherIndex);
        }
    }

    cout << operations.size() << '\n';
    for (auto &operation : operations)
        cout << operation.first + 1 << ' ' << operation.second + 1 << '\n';
}

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