Submission

Score: 20

User: VggT

Problemset: ประลอง

Language: cpp

Time: 0.002 second

Submitted On: 2025-10-16 11:04:11

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

void bt(vector<int> player,vector<int> &ans, vector<int> current, int sum, int &sumcurrent, int &mindiff, int size1, int index)
{
	if(current.size() == size1)
	{
		if(mindiff > abs((sum-sumcurrent)-sumcurrent))
		{
			ans = current;
			mindiff = abs((sum-sumcurrent)-sumcurrent);
		}
		return;
	}
	
	for(int i = index; i < player.size(); i++)
	{
		current.push_back(player[i]);
		sumcurrent+=player[i];
		bt(player,ans,current,sum,sumcurrent,mindiff,size1,i+1);
		current.pop_back();
		sumcurrent-=player[i];
	}
	
	return;
}

int main()
{
	cin.tie(0)->sync_with_stdio(0);
	int n;
	cin >> n;
	int size1 = 0, size2 = 0;
	if(n%2 != 0)
	{
		size1 = (n-1)/2;
		size2 = (n+1)/2;
	}
	else
	{
		size1 = n/2;
		size2 = n/2;
	}
	
	vector<int> team1;
	vector<int> team2;
	
	vector<int> player(n);
	
	int sum = 0;
	
	for(auto &a : player)
	{
		cin >> a;
		sum+=a;
	}
	
	vector<int> ans;
	vector<int> current;
	
	int currentsum = 0;
	
	int mindiff = INT_MAX;
	
	int sumcurrent = 0;
	
	bt(player,ans,current,sum,sumcurrent,mindiff,size1,0);
	
	team1 = ans;
	
	unordered_map<int,int> m;
	
	for(auto a : player) m[a]++;
	
	for(auto &a : team1)
	{
		m[a]--;
		if(m[a] == 0) m.erase(a);
	}
	
	for(auto l : m)
	{
		if(l.second > 0)
		{
			for(int i = 0; i < l.second; i++)
			{
				team2.push_back(l.first);
			}
		}
	}
	
	reverse(team2.begin(),team2.end());
	
	for(auto a : team1) cout << a << ' ';
	cout << '\n';
	for(auto a : team2) cout << a << ' ';
	
	
	return 0;
}