Submission #1132332

#	Time	Username	Problem	Language	Result	Execution time	Memory
1132332		c32ardash	Xor Sort (eJOI20_xorsort)	C++17	100 / 100	3 ms	840 KiB

xorsort

#include <bits/stdc++.h>

using namespace std;

const int NMAX=1e3+5, KMAX=4e4+5;
int v[NMAX], n, k;
struct swp{int i, j;}ans[KMAX];
struct srt{int v, o;}ord[NMAX];
bool cmp(srt a, srt b){return a.v<b.v;}

void solve1()
{
    for(int i=1;i<=n;i++)
        ord[i]={v[i], i};
    sort(ord+1, ord+n+1, cmp);
    for(int i=n;i>1;i--)
    {
        //xor each nr with the next except v[i]
        for(int j=1;j<i;j++)
        {
            v[j]^=v[j+1];
            ans[++k]={j, j+1};
        }
        //make the part before the maximum's position be max^v[j]
        for(int j=ord[i].o-2;j>=1;j--)
        {
            v[j]^=v[j+1];
            ans[++k]={j, j+1};
        }
        //make the part after the maximum's position be max^v[j], with max on v[n]
        for(int j=ord[i].o+1;j<=i;j++)
        {
            v[j]^=v[j-1];
            ans[++k]={j, j-1};
        }
        //decrease the 'positions' of future maximums
        for(int j=1;j<i;j++)
            if(ord[j].o>ord[i].o)
                ord[j].o--;
    }
    //restore the original values
    for(int i=n-1;i>=1;i--)
    {
        v[i]^=v[i+1];
        ans[++k]={i, i+1};
    }
}

bool check_if_sorted()
{
    for(int i=1;i<n;i++)
        if(v[i]>v[i+1])
            return 0;
    return 1;
}

void afisv(int c)
{
    if(c){
    if(check_if_sorted())
        cout<<"SORTED\n";
    else
        cout<<"NOT SORTED\n";}
    for(int i=1;i<=n;i++)
        cout<<v[i]<<" ";
    cout<<'\n';
}

void solve2(int l, int r, int b)
{
    //base case
    if(l>=r || b<0)
        return;
    //check for 0 and 1
    int f1=l-1, ok0=0;
    for(int i=l;i<=r;i++)
        if((v[i]&(1<<b))==0)
            ok0=1;
        else if(f1==l-1)
            f1=i;
    if(f1==l-1 || ok0==0)
    {
        solve2(l, r, b-1);
        return;
    }
    //make all (0, 1) before first (1, 1)
    for(int i=l;i<=f1-2;i++)
    {
        v[i]^=v[i+1];
        ans[++k]={i, i+1};
    }
    for(int i=f1-1;i>=l;i--)
    {
        v[i]^=v[i+1];
        ans[++k]={i, i+1};
    }
    //make all (0, 1) after first (1, 1) and transport (1, 1) to r
    int fn0=l-1;
    for(int i=f1;i<r;i++)
    {
        if(fn0==l-1)
            fn0=i;
        v[i]^=v[i+1];
        ans[++k]={i, i+1};
        if((v[i+1]&(1<<b))==0)
        {
            v[i+1]^=v[i];
            ans[++k]={i+1, i};
        }
        else if(i>l && (v[i-1]&(1<<b))>0)
        {
            v[i]^=v[i-1];
            ans[++k]={i, i-1};
        }
        else
            fn0=l-1;
    }
    if(f1==l)
        for(int i=fn0-1;i>=l;i--)
        {
            v[i]^=v[i+1];
            ans[++k]={i, i+1};
        }
    //make second half (1, 1)
    int mid=(l+r)/2;
    for(int i=r-1;i>mid;i--)
    {
        v[i]^=v[i+1];
        ans[++k]={i, i+1};
        v[i]^=v[i-1];
        ans[++k]={i, i-1};
    }
    //make first half (1, 0)
    for(int i=l;i<mid;i++)
    {
        v[i]^=v[i+1];
        ans[++k]={i, i+1};
    }
    for(int i=mid;i>=l;i--)
    {
        v[i]^=v[i+1];
        ans[++k]={i, i+1};
    }
    //solve for each half
    solve2(l, mid, b-1);
    solve2(mid+1, r, b-1);
}

void afis()
{
    cout<<k<<'\n';
    for(int i=1;i<=k;i++)
        cout<<ans[i].i<<" "<<ans[i].j<<'\n';
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int s;
    cin>>n>>s;
    for(int i=1;i<=n;i++)
        cin>>v[i];
    if(s==1)
        solve1();
    else
        solve2(1, n, 19);
    afis();
    return 0;
}

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