Submission

Score: 30

User: LT.

Problemset: ประลอง

Language: cpp

Time: 0.003 second

Submitted On: 2026-02-16 01:42:36

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

int main()
{
    int n;
    cin >> n;
    vector<pair<int, int>> arr(n); // {value, original_index}
    int totalSum = 0;

    for (int i = 0; i < n; i++)
    {
        cin >> arr[i].first;
        arr[i].second = i;
        totalSum += arr[i].first;
    }

    // Sort from high to low by value
    sort(arr.begin(), arr.end(), [](pair<int, int> a, pair<int, int> b)
         { return a.first > b.first; });

    vector<pair<int, int>> answer;
    vector<pair<int, int>> complement;
    int ansSum = 0;
    int compSum = 0;

    // Create working array, excluding middle element if n is odd
    vector<pair<int, int>> working;
    int middleIndex = n / 2;
    pair<int, int> middleValue;
    bool hasMiddle = false;

    for (int i = 0; i < n; i++)
    {
        if (n % 2 == 1 && i == middleIndex)
        {
            middleValue = arr[i];
            hasMiddle = true;
            continue; // Skip middle element
        }
        working.push_back(arr[i]);
    }

    // For every 2 elements, put 1 in answer and 1 in complement by balancing
    for (int i = 0; i < working.size(); i += 2)
    {
        // Decide which goes to answer and which to complement
        if (ansSum <= compSum)
        {
            answer.push_back(working[i]);
            ansSum += working[i].first;
            complement.push_back(working[i + 1]);
            compSum += working[i + 1].first;
        }
        else
        {
            complement.push_back(working[i]);
            compSum += working[i].first;
            answer.push_back(working[i + 1]);
            ansSum += working[i + 1].first;
        }
    }

    // If n is odd, put middle value back
    if (hasMiddle)
    {
        if (ansSum <= compSum)
        {
            answer.push_back(middleValue);
            ansSum += middleValue.first;
        }
        else
        {
            complement.push_back(middleValue);
            compSum += middleValue.first;
        }
    }

    // Sort back to original positions
    sort(answer.begin(), answer.end(), [](pair<int, int> a, pair<int, int> b)
         { return a.second < b.second; });
    sort(complement.begin(), complement.end(), [](pair<int, int> a, pair<int, int> b)
         { return a.second < b.second; });

    // cout << "Answer array: ";
    for (int i = 0; i < answer.size(); i++)
    {
        cout << answer[i].first;
        if (i < answer.size() - 1)
            cout << " ";
    }
    cout << '\n';

    // cout << "Complement array: ";
    for (int i = 0; i < complement.size(); i++)
    {
        cout << complement[i].first;
        if (i < complement.size() - 1)
            cout << " ";
    }
    cout << '\n';

    return 0;
}