Submission

Score: 90

User: dddrrrr

Problemset: ประลอง

Language: cpp

Time: 0.002 second

Submitted On: 2025-10-15 22:11:06

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

vector <int> ans1 ,ans2;
int mn = INT_MAX;

void backtrack(int i ,vector <int>& t1 ,vector <int>& t2 ,int sum1 ,int sum2 ,vector <int>& vec){
	int n = vec.size();
	//if(t1.size() > (n+1)/2 || t2.size() > (n+1)/2) return;

	if(i == n){
		if(abs(sum1 - sum2) < mn){
			ans1 = t1;
			ans2 = t2;
			mn = abs(sum1 - sum2);
		}
		return ;
	}

	
	if(t1.size() < (n+1)/2){
		t1.emplace_back(vec[i]);
		backtrack(i+1 ,t1 ,t2 ,sum1+vec[i] ,sum2 ,vec);
		t1.pop_back();
	}
	
	if(t2.size() < (n+1)/2){
		t2.emplace_back(vec[i]);
		backtrack(i+1 ,t1 ,t2 ,sum1 ,sum2+vec[i] ,vec);
		t2.pop_back();
	}
	return ;
}

int main(){
	cin.tie(0)->sync_with_stdio(0);
	int n;cin >> n;
	vector <int> vec(n);
	for(auto &i : vec)cin >> i;
	
	vector <int> t1 ,t2;
	backtrack(0 ,t1 ,t2 ,0 ,0 ,vec);
	
	for(auto i : ans2)cout << i << ' ';
	cout << "\n";
	for(auto i : ans1)cout << i << ' ';
	//cout << mn;
	
	return 0;
	
}