#include <bits/stdc++.h>
#include "partition.h"

using namespace std;

std::vector<int> solve(std::vector<int> A)
{
    int n=A.size();

    vector<int>pow(27,0);
    int currlg=1;
    for(int i=0;i<=25;i++)
    {
        pow[i]=currlg;
        currlg*=2;
    }

    vector<vector<int>>v(26);

    for(int i=0;i<n;i++)
    {
        if(A[i]==pow[0])
            v[0].push_back(i);
        else if(A[i]==pow[1])
            v[1].push_back(i);
        else if(A[i]==pow[2])
            v[2].push_back(i);
        else if(A[i]==pow[3])
            v[3].push_back(i);
        else if(A[i]==pow[4])
            v[4].push_back(i);
        else if(A[i]==pow[5])
            v[5].push_back(i);
        else if(A[i]==pow[6])
            v[6].push_back(i);
        else if(A[i]==pow[7])
            v[7].push_back(i);
        else if(A[i]==pow[8])
            v[8].push_back(i);
        else if(A[i]==pow[9])
            v[9].push_back(i);
        else if(A[i]==pow[10])
            v[10].push_back(i);
        else if(A[i]==pow[11])
            v[11].push_back(i);
        else if(A[i]==pow[12])
            v[12].push_back(i);
        else if(A[i]==pow[13])
            v[13].push_back(i);
        else if(A[i]==pow[14])
            v[14].push_back(i);
        else if(A[i]==pow[15])
            v[15].push_back(i);
        else if(A[i]==pow[16])
            v[16].push_back(i);
        else if(A[i]==pow[17])
            v[17].push_back(i);
        else if(A[i]==pow[18])
            v[18].push_back(i);
        else if(A[i]==pow[19])
            v[19].push_back(i);
        else if(A[i]==pow[20])
            v[20].push_back(i);
        else if(A[i]==pow[21])
            v[21].push_back(i);
        else if(A[i]==pow[22])
            v[22].push_back(i);
        else if(A[i]==pow[23])
            v[23].push_back(i);
        else if(A[i]==pow[24])
            v[24].push_back(i);
        else if(A[i]==pow[25])
            v[25].push_back(i);
    }

    /*for(int i=0;i<=25;i++)
    {
        cout<<i<<endl;
        for(int j : v[i])
            cout<<j<<' ';
        cout<<endl;
    }*/

    vector<int>l,r,p;

    if(n%2==1)
    {
        int idx=0;
        for(int i=0;i<=25;i++)
        {
            for(int j : v[i])
            {
                if(idx%2==0)
                    l.push_back(j);
                else
                    r.push_back(j);
                idx++;
            }
        }
        for(int i : l)
            p.push_back(i);
        for(int i : r)
            p.push_back(i);
    }
    else
    {
        int idx=0;
        for(int i=0;i<=25;i++)
        {
            for(int j : v[i])
            {
                if(idx%2==1)
                    l.push_back(j);
                else
                    r.push_back(j);
                idx++;
            }
        }
        for(int i : l)
            p.push_back(i);
        for(int i : r)
            p.push_back(i);
    }

    return p;
}
