Submission

---P--P---

Score: 20

User: fluke

Problemset: ประลอง

Language: cpp

Time: 0.003 second

Submitted On: 2025-03-12 20:48:51

#include <bits/stdc++.h>
#define ll long long
#define f first 
#define s second 
#define pii pair<int,int> 
#define emb emplace_back
#define em emplace
#define all(x) x.begin(),x.end()
#define DB cout<<"\n";system("pause");
using namespace std;

int n;
int per1,per2;
int best = 1e9+7;
vector <int> member1 , member2;
vector <int> power(101),qsum(101);

void dfs(int sum1,int sum2,int team1,int team2,vector <int> &team){

    // cout<<sum1<<" "<<sum2<<"\n";
    // cout<<team1<<" "<<team2<<"\n";
    // for(auto x : team)cout<<x<<" ";
    // DB

    if(team1 != per1 && team2 != per2){
        team[team1+team2] = 1;
        dfs(sum1+power[team1+team2],sum2,team1+1,team2,team);

        team[team1+team2] = 2;
        dfs(sum1,sum2+power[team1+team2],team1,team2+1,team);

        team[team1+team2] = 0;
    }
    else {
        if(team1 == per1){
            
            sum2 += qsum[n] - qsum[team1 + team2];
            
            if(abs(sum1 - sum2) < best){
                member1.clear();
                member2.clear();
                best = abs(sum1 - sum2);
                for(int i=0;i<n;i++){
                    if(team[i] == 1)member1.emb(power[i]);
                    else member2.emb(power[i]);
                }
            }


        }
        else {
            
            sum1 += qsum[n] - qsum[team1 + team2];

            if(abs(sum1 - sum2) < best){
                best = abs(sum1 - sum2);
                member1.clear();
                member2.clear();
                for(int i=0;i<n;i++){
                    if(team[i] == 2)member2.emb(power[i]);
                    else member1.emb(power[i]);
                }
            }

        }

    }
}

int main(){
ios::sync_with_stdio(false);cin.tie(0);
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>power[i];
        qsum[i+1] = qsum[i] +power[i];
    }

    if(n%2 == 0){
        per1 = n/2;
        per2 = n/2;
    }
    else {
        per1 = (n-1)/2;
        per2 = (n+1)/2;
    }
    vector <int> team(n);
    dfs(0,0,0,0,team);

    // cout<<best;
    // cout<<"\n";
    int sum1  = 0 ,sum2 = 0;
    for(int x  : member1){
        cout<<x<<" ";
        // sum1 += x;
    }
    // cout<<sum1;
    cout<<"\n";
    for(int x  : member2){
        cout<<x<<" ";
        // sum2 += x;
    }
    // cout<<sum2;
}