Submission #1117963

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117963		12345678	Xor Sort (eJOI20_xorsort)	C++17	100 / 100	6 ms	1140 KiB

xorsort

#include <bits/stdc++.h>

using namespace std;

const int nx=1e3+5;

int s, n, vs[nx], a[nx];
vector<pair<int, int>> res;

void solve(int sz)
{
    pair<int, pair<int, int>> mx;
    int cnt=0;
    for (int i=1; i<=n; i++) if (!vs[i]) mx=max(mx, {a[i], {i, ++cnt}});
    vs[mx.second.first]=1;
    //cout<<"debug "<<mx.second.first<<' '<<mx.second.second<<'\n';
    cnt=mx.second.second;
    for (int i=1; i<sz; i++) res.push_back({i, i+1});
    for (int i=cnt; i<sz; i++) res.push_back({i+1, i});
    for (int i=cnt-2; i>=1; i--) res.push_back({i, i+1});
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>s;
    for (int i=1; i<=n; i++) cin>>a[i];
    if (s==1)
    {
        for (int i=1; i<=n; i++) solve(n-i+1);
        for (int i=n-1; i>=1; i--) res.push_back({i, i+1});
    }
    else
    {
        int sz=n;
        for (int i=19; i>=0; i--)
        {
            for (int j=1; j<sz; j++)
            {
                if (a[j]&(1<<i))
                {
                    if (!(a[j+1]&(1<<i))) res.push_back({j+1, j}), a[j+1]^=a[j];
                    res.push_back({j, j+1}), a[j]^=a[j+1];
                }
            }
            if (a[sz]&(1<<i)) sz--;
        }
    }
    cout<<res.size()<<'\n';
    for (auto x:res) cout<<x.first<<' '<<x.second<<'\n';
}

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