Submission #467328

#	Time	Username	Problem	Language	Result	Execution time	Memory
467328		TlenekWodoru	Xor Sort (eJOI20_xorsort)	C++14	0 / 100	1 ms	332 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);**/
    cout<<a<<" "<<b<<endl;
    cout<<b<<" "<<a<<endl;
    cout<<a<<" "<<b<<endl;
    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)
                    {
                        cout<<a<<" "<<a+1<<endl;
                        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)
                    {
                        cout<<a<<" "<<a-1<<endl;
                        zaj[tab[a]]=0;
                        swap_true(a,a-1);
                        zaj[tab[a]]=1;
                    }
                }
            }
        }
    }
    else
    {
        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])
                {
                    cout<<a<<" "<<a+1<<endl;
                    swap_true(a,a+1);
                }
            }
            else
            {
                if(tab[a]>tab[a-1])
                {
                   cout<<a<<" "<<a-1<<endl;
                    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);
        }
    }
    /**for(int i=1;i<=n;i++)
    {
        cout<<tab[i]<<endl;
    }**/
    return 0;
}

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