Submission #441127

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

xorsort

#include <bits/stdc++.h>

using namespace std;
int n,s,v[100005];
bool get_bit(int val, int b)
{
    return ((val&(1<<b))!=0);
}
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++)
        {
            int poz = i;
            while(poz>1 && v[poz]<v[poz-1])
            {
                rez.push_back({poz,poz-1});
                v[poz]^=v[poz-1];
                rez.push_back({poz-1,poz});
                v[poz-1]^=v[poz];
                rez.push_back({poz,poz-1});
                v[poz]^=v[poz-1];
                --poz;
            }
        }
        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: 0 / 25
• Subtask 2: 0 / 35
• Subtask 3: 40 / 40