Submission #529290

#	Time	Username	Problem	Language	Result	Execution time	Memory
529290		Itamar	Xor Sort (eJOI20_xorsort)	C++14	0 / 100	0 ms	204 KiB

xorsort

#include <map>
using namespace std;
#include <vector>
#include <queue>
#include <set>
#include <algorithm>
#include <iostream>

vector<pair<int, int>> ans;
vector<int> v;
int k;

int main()
{
    int n, s;
    cin >> n >> s;
    v.resize(n);
    int siz = n;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        v[i] = x;
    }
    

     k = 0;
    int t = 1;
    while (t < 1e6) {
        t *= 2;
    }
    t = t / 2;
    bool f = 1;
    while (f) {
        for (int i = 0; i < siz; i++) {
            if (v[i] >= t) {
                f = 0;
                for (int j = i; j < siz - 1; j++) {
                    if (v[j] < t) {
                        v[j + 1] = v[j] ^ v[j + 1];
                        k++;
                        ans.push_back({ j + 1,j });
                    }
                }
                if (i >= siz / 2) {
                    for (int j = i - 1; j >= siz / 2; j--) {
                        v[j] = v[j] ^ v[j + 1];
                        k++;
                        ans.push_back({ j ,j + 1 });
                    }
                }
                else {
                    for (int j = i; j < siz / 2; j++) {
                        v[j] = v[j] ^ v[j + 1];
                        k++;
                        ans.push_back({ j ,j + 1 });
                    }
                }
                break;
            }
        }
        t /= 2;
    }
    f = 1;
    while (f) {
        f = 0;
        for (int i = 0; i < siz / 2 -1; i++) {
            if (v[i] >= v[i + 1]) {
                int c = v[i];
                v[i] = v[i + 1];
                v[i + 1] = c;
                ans.push_back({ i , i+1 });
                ans.push_back({ i+1 , i  });
                ans.push_back({ i , i + 1 });
                k += 3;
                f = 1;
            }
        }
    }
    f = 1;
    while (f) {
        f = 0;
        for (int i = siz/2; i < siz - 1; i++) {
            if (v[i] >= v[i + 1]) {
                int c = v[i];
                v[i] = v[i + 1];
                v[i + 1] = c;
                ans.push_back({ i , i + 1 });
                ans.push_back({ i + 1 , i });
                ans.push_back({ i , i + 1 });
                k += 3;
                f = 1;
            }
        }
    }
    cout << k << "\n";
    for (int i = 0; i < k; i++) {
        cout << ans[i].first+1 << ' ' << ans[i].second+1 << "\n";
    }
}

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