Submission #460752

#	Time	Username	Problem	Language	Result	Execution time	Memory
460752		Tenis0206	Xor Sort (eJOI20_xorsort)	C++11	100 / 100	8 ms	1032 KiB

xorsort

#include <bits/stdc++.h>

using namespace std;
int n,s,v[100005],aux[100005];
bool get_bit(int val, int b)
{
    return ((val&(1<<b))!=0);
}
void debug(int *a)
{
    for(int i=1;i<=n;i++)
    {
        cerr<<a[i]<<' ';
    }
    cerr<<'\n';
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>s;
    for(int i=1; i<=n; i++)
    {
        cin>>v[i];
    }
    if(s==1)
    {
        vector<pair<int,int>> rez;
        for(int i=1;i<=n;i++)
        {
            aux[i] = v[i];
        }
        for(int i=1;i<n;i++)
        {
            int poz = 0;
            for(int j=1;j<=n-i+1;j++)
            {
                if(aux[j]>aux[poz])
                {
                    poz = j;
                }
            }
            for(int j=1;j<=n-i;j++)
            {
                v[j]^=v[j+1];
                rez.push_back({j,j+1});
            }
            int x = aux[poz];
            for(int j=poz;j<n-i+1;j++)
            {
                aux[j] = aux[j+1];
            }
            aux[n-i+1] = x;
            for(int j=poz+1;j<=n-i+1;j++)
            {
                v[j]^=v[j-1];
                rez.push_back({j,j-1});
            }
            for(int j=poz-2;j>=1;j--)
            {
                v[j]^=v[j+1];
                rez.push_back({j,j+1});
            }
        }
        for(int i=n-1;i>=1;i--)
        {
            v[i]^=v[i+1];
            rez.push_back({i,i+1});
        }
        cout<<rez.size()<<'\n';
        for(auto it : rez)
        {
            cout<<it.first<<' '<<it.second<<'\n';
        }
        return 0;
    }
    vector<pair<int,int>> rez;
    for(int b=0; b<20; b++)
    {
        for(int i=2; i<=n; i++)
        {
            if(get_bit(v[i-1],b)==0)
            {
                continue;
            }
            if(get_bit(v[i],b)==1 && get_bit(v[i-1],b)==1)
            {
                rez.push_back({i-1,i});
                v[i-1]^=v[i];
                continue;
            }
            if(get_bit(v[i],b)==0 && get_bit(v[i-1],b)==1)
            {
                rez.push_back({i,i-1});
                v[i]^=v[i-1];
                rez.push_back({i-1,i});
                v[i-1]^=v[i];
            }
        }
    }
    cout<<rez.size()<<'\n';
    for(auto it : rez)
    {
        cout<<it.first<<' '<<it.second<<'\n';
    }
    return 0;
}

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