Submission

----------

Score: 0

User: pxsit

Problemset: Path Finding

Language: cpp

Time: 0.002 second

Submitted On: 2025-03-12 13:35:35

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <cmath>
#include <climits>

using namespace std;

int main()
{
    // Read input
    int n;
    cin >> n;

    vector<long long> units(n);
    for (int i = 0; i < n; i++)
    {
        cin >> units[i];
    }

    // Get total sum of all units
    long long totalSum = 0;
    for (auto val : units)
    {
        totalSum += val;
    }

    // Create pairs of (value, index) for sorting
    vector<pair<long long, int>> unitWithIndex;
    for (int i = 0; i < n; i++)
    {
        unitWithIndex.push_back({units[i], i});
    }

    // Sort by value in descending order
    sort(unitWithIndex.begin(), unitWithIndex.end(), greater<pair<long long, int>>());

    // Initialize teams (storing indices)
    vector<int> team1, team2;
    long long sum1 = 0, sum2 = 0;

    // Assign units to teams greedily
    for (const auto &unit : unitWithIndex)
    {
        if (sum1 <= sum2)
        {
            team1.push_back(unit.second);
            sum1 += unit.first;
        }
        else
        {
            team2.push_back(unit.second);
            sum2 += unit.first;
        }
    }

    // Determine team sizes based on whether n is odd or even
    int team1Size = n / 2;
    int team2Size = n - team1Size;

    // Adjust team sizes if necessary
    if (team1.size() > team1Size)
    {
        // Move units from team1 to team2
        while (team1.size() > team1Size)
        {
            // Find best unit to move
            long long bestDiff = LLONG_MAX;
            int bestIndex = -1;

            for (int i = 0; i < team1.size(); i++)
            {
                int unitIndex = team1[i];
                long long unitValue = units[unitIndex];

                // Calculate difference if we move this unit
                long long newSum1 = sum1 - unitValue;
                long long newSum2 = sum2 + unitValue;
                long long newDiff = abs(newSum1 - newSum2);

                if (newDiff < bestDiff)
                {
                    bestDiff = newDiff;
                    bestIndex = i;
                }
            }

            // Move the best unit
            int unitIndex = team1[bestIndex];
            long long unitValue = units[unitIndex];
            sum1 -= unitValue;
            sum2 += unitValue;
            team2.push_back(unitIndex);
            team1.erase(team1.begin() + bestIndex);
        }
    }
    else if (team2.size() > team2Size)
    {
        // Move units from team2 to team1
        while (team2.size() > team2Size)
        {
            // Find best unit to move
            long long bestDiff = LLONG_MAX;
            int bestIndex = -1;

            for (int i = 0; i < team2.size(); i++)
            {
                int unitIndex = team2[i];
                long long unitValue = units[unitIndex];

                // Calculate difference if we move this unit
                long long newSum1 = sum1 + unitValue;
                long long newSum2 = sum2 - unitValue;
                long long newDiff = abs(newSum1 - newSum2);

                if (newDiff < bestDiff)
                {
                    bestDiff = newDiff;
                    bestIndex = i;
                }
            }

            // Move the best unit
            int unitIndex = team2[bestIndex];
            long long unitValue = units[unitIndex];
            sum1 += unitValue;
            sum2 -= unitValue;
            team1.push_back(unitIndex);
            team2.erase(team2.begin() + bestIndex);
        }
    }

    // Try to improve the solution with some swaps
    bool improved = true;
    while (improved)
    {
        improved = false;

        for (int i = 0; i < team1.size() && !improved; i++)
        {
            for (int j = 0; j < team2.size() && !improved; j++)
            {
                int unit1Index = team1[i];
                int unit2Index = team2[j];

                long long val1 = units[unit1Index];
                long long val2 = units[unit2Index];

                // Calculate current difference
                long long currDiff = abs(sum1 - sum2);

                // Calculate new difference if we swap
                long long newSum1 = sum1 - val1 + val2;
                long long newSum2 = sum2 - val2 + val1;
                long long newDiff = abs(newSum1 - newSum2);

                // If swap improves balance, do it
                if (newDiff < currDiff)
                {
                    sum1 = newSum1;
                    sum2 = newSum2;
                    swap(team1[i], team2[j]);
                    improved = true;
                }
            }
        }
    }

    // Create boolean array to track which units are in team1
    vector<bool> inTeam1(n, false);
    for (int idx : team1)
    {
        inTeam1[idx] = true;
    }

    // Output according to original input order
    // Team 1 first
    bool first = true;
    for (int i = 0; i < n; i++)
    {
        if (inTeam1[i])
        {
            if (!first)
                cout << " ";
            cout << units[i];
            first = false;
        }
    }
    cout << endl;

    // Team 2
    first = true;
    for (int i = 0; i < n; i++)
    {
        if (!inTeam1[i])
        {
            if (!first)
                cout << " ";
            cout << units[i];
            first = false;
        }
    }
    cout << endl;

    return 0;
}