Submission #467089

#	Time	Username	Problem	Language	Result	Execution time	Memory
467089		TlenekWodoru	Xor Sort (eJOI20_xorsort)	C++14	0 / 100	4 ms	332 KiB

xorsort

#include <bits/stdc++.h>
using namespace std;
int tab[1009];
vector<pair<int,int>>odp;
int dp[1009][1009];
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];
    }
    for(int i=1;i<=1500;i++)
    {
        int a=rand()%n+1;
        int b=rand()%2;
        if(a==1||b==1)
        {
            odp.push_back({a,a+1});
            swap_true(a,b);
        }
        else if(a==n||b==0)
        {
            odp.push_back({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:76: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]
   76 |     for(int i=0;i<odp.size();i++)
      |                 ~^~~~~~~~~~~

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