Submission #458005

#	Time	Username	Problem	Language	Result	Execution time	Memory
458005		RaresFelix	Xor Sort (eJOI20_xorsort)	C++17	100 / 100	13 ms	5076 KiB

xorsort

#include <bits/stdc++.h>
#define MN 10071
#define ML 20
using namespace std;
int n, s, A[MN], B[MN];
int F[(1<<21)];
vector<pair<int, int> > SOL;
void xo(int a, int b) {
    --F[A[a]];
    A[a] ^= A[b];
    ++F[A[a]];
    SOL.push_back({a, b});
}
int main() {
    cin >> n >> s;
    for(int i = 1; i <= n; ++i)
        cin >> A[i];
    if(s == 1 || n <= ML){
        for(int i = 1; i <= n; ++i) B[i] = A[i];
        for(int i = 1; i < n; ++i) xo(i, i+1);
        int pma = 0;
        for(int i = 0; i < n-1; ++i){
            pma = 0;
            for(int j = 1; j <= n - i; ++j)
                if(B[j] > B[pma]) pma = j;
            for(int j = pma+1; j <= n - i; ++j){
                xo(j, j-1);
                swap(B[j], B[j-1]);
            }
            for(int j = max(pma-1, 1); j < n-i; ++j)
                xo(j, j+1);
        }
    } else {
        for(int j = (ML-1); j >= 0; --j){
            for(int i = 1; i < n + j - (ML-1); ++i){
                if((A[i] & (1<<j)) && A[i+1] & (1<<j)) xo(i, i + 1);
                else if((A[i] & (1<<j))){
                    xo(i+1, i);
                    xo(i, i + 1);
                }
            }
        }
    }
//    for(int i = 1; i <= n; ++i)
//        cout << A[i] << " \n"[i==n];
    cout << SOL.size() << "\n";
    for(auto it : SOL) cout << it.first << " " << it.second << "\n";
    return 0;
}

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