Submission #467169

#	Time	Username	Problem	Language	Result	Execution time	Memory
467169		TlenekWodoru	Xor Sort (eJOI20_xorsort)	C++14	60 / 100	1094 ms	12700 KiB

xorsort

#include <bits/stdc++.h>
using namespace std;
int tab[1009];
bool zaj[1100000];
vector<pair<int,int>>odp;
int xorr(int a, int b)
{
    int u=1;
    int wynik=0;
    while(a>0||b>0)
    {
        if(a%2!=b%2)
        {
            wynik+=u;
        }
        a=a/2;
        b=b/2;
        u=u*2;
    }
    return wynik;
}
void swap_true(int a, int b)
{
    tab[a]=xorr(tab[a],tab[b]);
}
void swapp(int a, int b)
{
    /**swap_true(a,b);
    swap_true(b,a);
    swap_true(a,b);**/
    odp.push_back({a,b});
    odp.push_back({b,a});
    odp.push_back({a,b});
    swap(tab[a],tab[b]);
}
int main()
{ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    srand(time(0));
    int n,s;cin>>n>>s;
    for(int i=1;i<=n;i++)
    {
        cin>>tab[i];
        zaj[tab[i]]=1;
    }
    if(s==1)
    {
        for(int i=1;i<=n*3;i++)
        {
            int a=(rand()%n)+1;
            int b=rand()%2;
            if(a==1||(b%2==1&&a!=n))
            {
                if(tab[a]>tab[a+1])
                {
                    if(zaj[xorr(tab[a],tab[a+1])]==0)
                    {
                        odp.push_back({a,a+1});
                        zaj[tab[a]]=0;
                        swap_true(a,a+1);
                        zaj[tab[a]]=1;
                    }
                }
            }
            else
            {
                if(tab[a]>tab[a-1])
                {
                    if(zaj[xorr(tab[a],tab[a-1])]==0)
                    {
                        odp.push_back({a,a-1});
                        zaj[tab[a]]=0;
                        swap_true(a,a-1);
                        zaj[tab[a]]=1;
                    }
                }
            }
        }
    }
    else
    {
        for(int i=1;i<=n*2;i++)
        {
            int a=(rand()%n)+1;
            int b=rand()%2;
            if(a==1||(b%2==1&&a!=n))
            {
                if(tab[a]>tab[a+1])
                {
                    odp.push_back({a,a+1});
                    swap_true(a,a+1);
                }
            }
            else
            {
                if(tab[a]>tab[a-1])
                {
                    odp.push_back({a,a-1});
                    swap_true(a,a-1);
                }
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        int minn=2000000000;
        int ind=-1;
        for(int j=i;j<=n;j++)
        {
            if(tab[j]<minn)
            {
                minn=tab[j];
                ind=j;
            }
        }
        for(int j=ind;j-1>=i;j--)
        {
            swapp(j,j-1);
        }
    }
    cout<<odp.size()<<endl;
    for(int i=0;i<odp.size();i++)
    {
        cout<<odp[i].first<<" "<<odp[i].second<<endl;
    }
    /**for(int i=1;i<=n;i++)
    {
        cout<<tab[i]<<endl;
    }**/
    return 0;
}

Compilation message (stderr)

xorsort.cpp: In function 'int main()':
xorsort.cpp:121:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |     for(int i=0;i<odp.size();i++)
      |                 ~^~~~~~~~~~~

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