Shared code

#include <bits/stdc++.h>
using namespace std;

#define int int64_t
#define pii array<int,2>

const int MAXN = (1<<20);
pii p1[MAXN], p2[MAXN];
int t1, t2;

pair<vector<int>, vector<int>> reconstruct(vector<int> &a, int mask1, int mask2) {
    vector<int> v1, v2;
    for (int i=0;i<(int)a.size();i++) {
        if ((mask1 & (1<<i)) != 0) v1.push_back(a[i]);
        if ((mask2 & (1<<i)) != 0) v2.push_back(a[i]);
    }
    return make_pair(v1, v2);
}


struct Data {
    vector<int> a1, a2;
    int p1s, p2s;

    void calc(vector<int> &a, pii *p, int &ps) {
        int n = (int)a.size();
        ps = (((int)1)<<n);
        for (int i=0;i<(1<<n);i++) {
            int sum = 0;
            for (int j=0;j<n;j++) {
                if (((1<<j) & i) != 0) sum += a[j];
            }
            p[i] = {sum, i};
        }

        sort(p, p+ps);
    }

    Data(vector<int> &v1, vector<int> &v2) {
        a1 = v1;
        a2 = v2;

        calc(a1, p1, p1s);
        calc(a2, p2, p2s);
    }

    int countSubsets(int bound) {
        t1 = 0, t2 = p2s - 1;

        int sum = 0;
        for (;t2 >= 0; t2--) {
            while (t1 < p1s && p2[t2][0] + p1[t1][0] <= bound) t1++;

            sum += t1;
        }

        return sum - 1;
    }

    pair<vector<int>, vector<int>> findTwoSubsets(int sum) {
        t1 = 0, t2 = p2s - 1;
        
        vector<pii> vv;
        for (;t2 >= 0 && vv.size() < 2; t2--) {
            while (t1 < p1s && p2[t2][0] + p1[t1][0] <= sum) {
                if (p1[t1][0] + p2[t2][0] == sum) {
                    vv.push_back({p1[t1][1], p2[t2][1]});
                }

                if (vv.size() >= 2) break;
                t1++;
            }
        }

        auto v1 = reconstruct(a1, vv[0][0], vv[1][0]);
        auto v2 = reconstruct(a2, vv[0][1], vv[1][1]);

        for (auto &x:v2.first) v1.first.push_back(x);
        for (auto &x:v2.second) v1.second.push_back(x);
        return v1;
    }
};


signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;cin>>n;
    vector<int> a(n);
    for (auto &x:a)cin>>x;

    vector<int> a1, a2;
    for (int i=0;i<n;i++) {
        if (i % 2 == 0) a1.push_back(a[i]);
        else a2.push_back(a[i]);
    }

    Data d(a1, a2);

    pair<vector<int>, vector<int>> res;
    bool fnd = false;
    for (int i=1;i<d.p1s && (!fnd);i++) {
        if (p1[i][0] == p1[i-1][0]) {
            res = reconstruct(a1, p1[i][1], p1[i-1][1]);
            fnd = true;
        }
    }

    for (int i=1;i<d.p2s && (!fnd);i++) {
        if (p2[i][0] == p2[i-1][0]) {
            res = reconstruct(a2, p2[i][1], p2[i-1][1]);
            fnd = true;
        }
    }

    if (!fnd) {
        // clock_t subStart = clock();
        int l = 1, r = (((int)1)<<n) - 2;
        int ans = -1;
        while (l <= r) {
            int m = l + (r-l)/2;

            if (d.countSubsets(m) > m) {
                ans = m;
                r = m-1;
            }

            else {
                l = m+1;
            }
        }

        res = d.findTwoSubsets(ans);
    }

    vector<int> v1 = res.first, v2 = res.second;
    sort(v1.begin(), v1.end());
    sort(v2.begin(), v2.end());

    vector<int> toRem;
    auto findPos=[&](vector<int> &v, int val) {
        for (int i=0;i<(int)v.size();i++) {
            if (v[i] == val) return i;
        }
        
        return (int)-1;
    };

    for (auto &x:v1) {
        int ps = findPos(v2, x);
        if (ps != -1) {
            v2.erase(v2.begin() + ps);
            toRem.push_back(x);
        }
    }

    for (auto &x:toRem) {
        int ps = findPos(v1, x);
        v1.erase(v1.begin() + ps);
    }

    auto print=[&](vector<int> &v) {
        cout << v.size() << endl;
        for (auto &x:v) cout << x << " ";
        cout << "\n";
    };

    print(v1);
    print(v2);
}