Submission

Score: 100

User: nate213121

Problemset: ประลอง

Language: cpp

Time: 0.002 second

Submitted On: 2026-09-06 15:02:38

#include <climits>
#include <cstdlib>
#include <iostream>
#include <vector>
using namespace std;

int n, team1Size;
vector<long long> strength;
vector<char> chosen, bestChosen;

long long totalStrength = 0;
long long bestDifference = LLONG_MAX;
long long theoreticalBest;

void searchTeam1(int index, int taken, long long team1Sum) {
    // This difference cannot be improved.
    if (bestDifference == theoreticalBest) return;

    // Team 1 is complete: evaluate its difference.
    if (taken == team1Size) {
        long long difference =
            llabs(totalStrength - 2 * team1Sum);

        if (difference < bestDifference) {
            bestDifference = difference;
            bestChosen = chosen;
        }
        return;
    }

    // No input remains, or too few units remain.
    if (index == n ||
        taken + (n - index) < team1Size) {
        return;
    }

    // Choice 1: leave this unit for Team 2.
    chosen[index] = false;
    searchTeam1(index + 1, taken, team1Sum);

    // Choice 2: put this unit in Team 1.
    chosen[index] = true;
    searchTeam1(
        index + 1,
        taken + 1,
        team1Sum + strength[index]
    );
    chosen[index] = false; // Backtrack.
}

void printTeam(bool printChosen) {
    bool first = true;

    for (int i = 0; i < n; ++i) {
        if (static_cast<bool>(bestChosen[i]) == printChosen) {
            if (!first) cout << ' ';
            cout << strength[i];
            first = false;
        }
    }

    cout << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    strength.resize(n);

    for (long long &value : strength) {
        cin >> value;
        totalStrength += value;
    }

    team1Size = n / 2;
    theoreticalBest = llabs(totalStrength) % 2;

    chosen.assign(n, false);
    bestChosen.assign(n, false);

    searchTeam1(0, 0, 0);

    printTeam(true);
    printTeam(false);
}