Submission

Score: 100

User: nate213121

Problemset: ประลอง

Language: cpp

Time: 0.002 second

Submitted On: 2026-09-06 16:24:39

#include <bits/stdc++.h>

using namespace std;

int n;
vector<int> units;
vector<int> currTeams;
vector<int> bestTeams;
int totalSum = 0;
int currDiff;
int bestDiff = INT_MAX;
int theoreticalBestDiff;

void recurse(int team1Size, int team1Sum, int index)
{
    currDiff = abs(team1Sum - (totalSum - team1Sum));
    if(team1Size == (n / 2))
    {
        if(currDiff < bestDiff)
        {
            bestTeams = currTeams;
            bestDiff = currDiff;
        }
        return;
    }

    if(bestDiff == theoreticalBestDiff)
    {
       return;
    }
    if(index == n)
    {
        return;
    }
    if(team1Size + (n - index) < (n / 2))
    {
        return;
    }

    currTeams[index] = 2;
    recurse(team1Size, team1Sum, index + 1);
    currTeams[index] = 1;
    recurse(team1Size + 1, team1Sum + units[index], index + 1);
    currTeams[index] = 2;
}

int main()
{
    cin >> n;
    units.resize(n);
    currTeams.resize(n, 2);
    bestTeams.resize(n);
    for(int i = 0; i < n; i++)
    {
        cin >> units[i];
        totalSum += units[i];
    }
    theoreticalBestDiff = totalSum % 2;
    
    recurse(0, 0, 0);

    for(int i = 0; i < n; i++)
    {
        if(bestTeams[i] == 1)
        {
            cout << units[i] << " ";
        }
    }
    cout << endl;
    for(int i = 0; i < n; i++)
    {
        if(bestTeams[i] == 2)
        {
            cout << units[i] << " ";
        }
    }
    
    return 0;
}