Submission

Compilation Error

Score: 0

User: pxsit

Problemset: ประลอง

Language: cpp

Time: 0.000 second

Submitted On: 2025-03-12 13:22:16

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

using namespace std;

// Function to find the optimal division of units
pair<vector<int>, vector<int>> divideUnits(const vector<int>& units) {
    int n = units.size();
    vector<int> originalIndices(n);
    for (int i = 0; i < n; i++) {
        originalIndices[i] = i;
    }
    
    // Get total sum of all units
    long long totalSum = 0;
    for (int val : units) {
        totalSum += val;
    }
    
    // Target sum for each team
    long long targetSum = totalSum / 2;
    
    // Create a copy of units for sorting
    vector<pair<int, 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(), [](auto& a, auto& b) {
        return a.first > b.first;
    });
    
    // Initialize teams
    vector<int> team1, team2;
    long long sum1 = 0, sum2 = 0;
    
    // Assign units to teams greedily
    for (const auto& [value, index] : unitWithIndex) {
        if (sum1 <= sum2) {
            team1.push_back(index);
            sum1 += value;
        } else {
            team2.push_back(index);
            sum2 += value;
        }
    }
    
    // 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
            int bestDiff = INT_MAX;
            int bestIndex = -1;
            
            for (int i = 0; i < team1.size(); i++) {
                int unitIndex = team1[i];
                int 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];
            int 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
            int bestDiff = INT_MAX;
            int bestIndex = -1;
            
            for (int i = 0; i < team2.size(); i++) {
                int unitIndex = team2[i];
                int 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];
            int 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(); i++) {
            for (int j = 0; j < team2.size(); j++) {
                int unit1 = team1[i];
                int unit2 = team2[j];
                
                int val1 = units[unit1];
                int val2 = units[unit2];
                
                // 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;
                    break;
                }
            }
            if (improved) break;
        }
    }
    
    // Sort team arrays by original indices
    vector<int> sortedTeam1(team1.size()), sortedTeam2(team2.size());
    for (int i = 0; i < team1.size(); i++) {
        sortedTeam1[i] = team1[i];
    }
    for (int i = 0; i < team2.size(); i++) {
        sortedTeam2[i] = team2[i];
    }
    
    return {sortedTeam1, sortedTeam2};
}

int main() {
    // Read input
    int n;
    cin >> n;
    
    vector<int> units(n);
    for (int i = 0; i < n; i++) {
        cin >> units[i];
    }
    
    // Get the division
    auto [team1Indices, team2Indices] = divideUnits(units);
    
    // Output team 1
    for (int i = 0; i < team1Indices.size(); i++) {
        cout << units[team1Indices[i]];
        if (i < team1Indices.size() - 1) {
            cout << " ";
        }
    }
    cout << endl;
    
    // Output team 2
    for (int i = 0; i < team2Indices.size(); i++) {
        cout << units[team2Indices[i]];
        if (i < team2Indices.size() - 1) {
            cout << " ";
        }
    }
    cout << endl;
    
    return 0;
}