Submission #1135152

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135152		RaduM	Xor Sort (eJOI20_xorsort)	C++20	60 / 100	5 ms	964 KiB

xorsort

#include <bits/stdc++.h>

using namespace std;

int v[1005];
map <int, int> mp;
vector < pair <int, int> > sol;

void divide(int st, int dr){
    if(st == dr) return;
    int b2 = -1, p = 0;
    for(int i = st; i <= dr; i++){
        if(31 - __builtin_clz(v[i]) > b2){
            b2 = 31 - __builtin_clz(v[i]);
            p = i;
        }
    }
    if(b2 < 0) return;
    for(int i = p; i < dr; i++){
        if((1 << b2) & v[i + 1]){
            sol.push_back({i, i + 1});
            v[i] ^= v[i + 1];
        }
        else{
            sol.push_back({i + 1, i});
            v[i + 1] ^= v[i];
            sol.push_back({i, i + 1});
            v[i] ^= v[i + 1];
        }
    }
    divide(st, dr - 1);
}

//int v2[1002];

int main()
{
    int n,i,c,k;
    // ios_base::sync_with_stdio(false);
    // cin.tie(nullptr);
    cin >> n >> c;
    for(i = 1; i <= n; i++) cin >> v[i];
    if(c == 1){
        k = 0;
        for(i = 1; i <= n; i++) mp[v[i]] = 1;
        for(auto &x : mp) x.second = ++k;
        for(i = 1; i <= n; i++) v[i] = mp[v[i]];
        for(i = 1; i < n; i++) sol.push_back({i, i + 1});
        for(i = n; i >= 2; i--){
            int p = 0;
            for(p = 1; p < i; p++){
                if(v[p] == i) break;
            }
            for(int j = p; j < i; j++){
                sol.push_back({j + 1, j});
                swap(v[j], v[j + 1]);
            }
            for(int j = max(1, p - 1); j < i; j++) sol.push_back({j, j + 1});
        }
        cout << (int)sol.size() << "\n";
        for(auto x : sol) cout << x.first << " " << x.second << "\n";
        return 0;
    }
//    for(i = 1; i <= n; i++) v2[i] = v[i];
    divide(1, n);
    cout << (int)sol.size() << "\n";
    for(auto x : sol) cout << x.first << " " << x.second << "\n";
//    for(auto x : sol) v2[x.first] ^= v2[x.second];
//    for(i = 1; i <= n; i++) cout << v2[i] << " ";
    return 0;
}

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