#include "partition.h"
#include<bits/stdc++.h>
using namespace std;
std::vector<int> solve(std::vector<int> A)
{
    vector<int> ans1;
    vector<int> ans2;
    vector<pair<int,int>> a;
    for(int i=0; i<A.size(); i++)
    {
        a.push_back({A[i],i});
    }
    set<pair<int,int>> v1,v2;
    int sumtot=0,sumv2=0;
    sort(a.begin(),a.end());
    int last=0;
    for(int i=0; i<a.size()/2-1; i++)
    {
        sumtot+=a[i].first;
        v1.insert(a[i]);
    }
    if(A.size()%2==0)
    {
        v2.insert(a[a.size()/2-1]);
        sumtot+=a[A.size()/2-1].first;
        sumv2+=a[A.size()/2-1].first;
    }
    else
    {
        v1.insert(a[A.size()/2-1]);
        sumtot+=a[A.size()/2-1].first;
    }
    for(int i=A.size()/2; i<A.size(); i++)
    {
        sumtot+=a[i].first;
        sumv2+=a[i].first;
        v2.insert(a[i]);
    }
    bool ok=0;
    while(!v1.empty() && !v2.empty())
    {
        pair<int,int> it=*v1.begin();
        pair<int,int> it2=*v2.begin();
        if(sumv2-A[it2.second]+A[it.second]>sumtot/2)
        {
            v2.erase(it2);
            v1.erase(it);
            ans2.push_back(it.second);
            v1.insert(it2);
            sumv2=sumv2-A[it2.second]+A[it.second];
        }
        else
        {
            ans1.push_back(it.second);
            v1.erase(it);
        }
    }
    while(!v2.empty())
    {
        pair<int,int> it=*v2.begin();
        ans2.push_back(it.second);
        v2.erase(it);
    }
    while(!v1.empty()){
    pair<int,int> it=*v1.begin();
    ans1.push_back(it.second);
        v1.erase(it);
    }
    for(int i=0;i<ans1.size();i++){
    ans2.push_back(ans1[i]);
    }
    return ans2;
}

