Submission #1104399

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104399		ziyad_alharbi	Xor Sort (eJOI20_xorsort)	C++17	0 / 100	1 ms	336 KiB

xorsort

#include<bits/stdc++.h>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n,t;
    cin>>n>>t;
    int a[n+5],b[n+5],c[n+5];
    set<pair<int,int>>st;
    for(int x=1;x<=n;x++)
    {
        cin>>a[x];
        st.insert({a[x],x});
        b[x]=a[x];
        c[x]=a[x];
    }
    sort(c+1,c+1+n);
    vector<pair<int,int>>ans;
    if(t==1)
    {
        int I=n;
        for(int x=n;x>=1;x--)
        {
            if(a[x]==c[x])
            {
                st.erase({a[x],x});
                I--;
            }
            else
            {
                break;
            }
        }
        for(int x=1;x<I;x++)
        {
            ans.push_back({x,x+1});
            b[x]=(b[x]^b[x+1]);
        }
        
        while(st.size())
        {
            auto [v,i]=*st.rbegin();
            st.erase({v,i});
            if(i==I)
            {
                I--;
                continue;
            }
            //cout<<v<<' '<<i<<'\n';
            for(int x=i-1;x>1;x--)
            {
                ans.push_back({x-1,x});
                b[x-1]=(b[x-1]^b[x]);
            }
            for(int x=i+1;x<=I;x++)
            {
                ans.push_back({x,x-1});
                b[x]=(b[x]^b[x-1]);
            }
            for(int x=2;x<=I;x++)
            {
                ans.push_back({x-1,x});
                b[x-1]=(b[x-1]^b[x]);
                if(x>i)
                {
                    st.erase({a[x],x});
                    swap(a[x],a[x-1]);
                    st.insert({a[x-1],x-1});
                }
            }
            I--;
        }
    }
    /*for(int x=1;x<=n;x++)
    {
        cout<<b[x]<<' ';
    }
    cout<<'\n';*/
    cout<<ans.size()<<'\n';
    for(auto [x,y]:ans)cout<<x<<' '<<y<<'\n';
}

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