Submission #529274

#	Time	Username	Problem	Language	Result	Execution time	Memory
529274		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> a;
int k;
void calc(vector<int> v, int t) {
    int siz = v.size();
    bool f = 0;
    if (v.size() > 1) {
        for (int i = 0; i < siz; i++) {
            if (v[i] >= t) {
                f = 1;
                for (int j = i; j < siz - 1; j++) {
                    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;
            }
        }

        if (f) {
            vector<int> v1;
            vector<int> v2;
            for (int i = 0; i < siz / 2; i++) {
                v1.push_back(v[i]);
            }
            for (int i = siz / 2; i < siz; i++) {
                v2.push_back(v[i]);
            }
            calc(v1, t / 2);
            calc(v2, t / 2);
        }
        else {
            calc(v, t / 2);
        }
    }
}
int main()
{
    int n, s;
    cin >> n >> s;
    a.resize(n);
    int siz = n;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        a[i] = x;
    }
    

     k = 0;
    int t = 1;
    while (t < 1e6) {
        t *= 2;
    }
    t = t / 2;
    calc(a, t);
    cout << k << "\n";
    for (int i = 0; i < k; i++) {
        cout << ans[i].first+1 << ' ' << ans[i].second+1 << "\n";
    }
}

Compilation message (stderr)

xorsort.cpp: In function 'int main()':
xorsort.cpp:63:9: warning: unused variable 'siz' [-Wunused-variable]
   63 |     int siz = n;
      |         ^~~

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