Submission #1248379

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248379		andrei_n	Xor Sort (eJOI20_xorsort)	C++20	100 / 100	4 ms	968 KiB

xorsort

#include <bits/stdc++.h>

using namespace std;

mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());
int rng(int a, int b)
{
    return uniform_int_distribution<int>(a, b)(mt);
}

int v[1005];
vector<pair<int,int>> ans;

void solve2(int n, int bit)
{
    if(n == 1) return;
    if(bit == -1) return;
    int first1 = 0;
    for(int i=1; i<=n; ++i)
        if(v[i] & (1<<bit))
        {
            if(!first1)
                first1 = i;
        }
        else if(first1)
        {
            ans.emplace_back(i, i-1);
            v[i] ^= v[i-1];
            assert(v[i] & (1<<bit));
        }
    if(first1)
    {
        for(int i=first1; i<n; ++i)
        {
            ans.emplace_back(i, i+1);
            v[i] ^= v[i+1];
            assert(!(v[i] & (1<<bit)));
        }
        solve2(n-1, bit-1);
        assert(v[n] & (1<<bit));
    }
    else
        solve2(n, bit-1);
}

void doXor(int a, int b)
{
    assert(abs(a - b) == 1);
    v[a] ^= v[b];
    ans.emplace_back(a, b);
}

void xorSwap(int p)
{
    ans.emplace_back(p, p+1);
    ans.emplace_back(p+1, p);
    ans.emplace_back(p, p+1);
    swap(v[p], v[p+1]);
}

void solve1(int n)
{
    for(int i=1; i<=n; ++i)
        if(v[i] == 0)
        {
            for(int j=i; j<n; ++j)
                xorSwap(j);
            --n;
            break;
        }
    for(int cnt=0; cnt<10; ++cnt)
    {
        int nr = rng(1, max(n/2, min(n, 10)));
//        cout<<nr<<'\n';
        for(int i=nr-1; i>=1; --i)
            xorSwap(i);
//            for(int i=1; i<=n; ++i)
//        cout<<v[i]<<' ';
//    cout<<endl;
        for(int i=1; i<n; ++i)
        {
            doXor(i, i+1);
            doXor(i+1, i);
        }
    }
//    for(int i=1; i<=n; ++i)
//        cout<<v[i]<<' ';
//    cout<<endl;
    int ok;
    do
    {
        ok = 1;
        for(int i=1; i<n; ++i)
            if(v[i] > v[i+1])
            {
                xorSwap(i);
                ok = 0;
            }
    }
    while(!ok);
}

signed main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n,s; cin>>n>>s;
    for(int i=1; i<=n; ++i)
        cin>>v[i];
    if(s == 2)
        solve2(n, 19);
    else
        solve1(n);
//    for(int i=1; i<=n; ++i)
//        cout<<v[i]<<' ';
    cout<<ans.size()<<'\n';
    for(auto &i : ans)
        cout<<i.first<<' '<<i.second<<'\n';
//    for(int i=1; i<=n; ++i)
//        cout<<v[i]<<' ';
    return 0;
}

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