Submission

Score: 30

User: spammer_destroyer

Problemset: ประลอง

Language: cpp

Time: 0.002 second

Submitted On: 2025-10-20 12:22:27

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int test(vector<int> x1,vector<int> x2, int n, int n1) {
  int i,dif=0;
  for(i=0;i<n1;i++) {
    //cout << x1[i] << " ";
    dif+=x1[i];
  }
  //cout << "\n";
  for(i=0;i<n-n1;i++) {
    //cout << x2[i] << " ";
    dif-=x2[i];
  }
  //cout << "/dif=" << dif << "\n";
  return dif;
}
void copy(vector<int>& min_x1, vector<int>& min_x2, vector<int> x1, vector<int> x2, int n, int n1) {
  int i;
  for(i=0;i<n1;i++) {
    min_x1[i]=x1[i];
  }
  for(i=0;i<n-n1;i++) {
    min_x2[i]=x2[i];
  }
}
void show(vector<int> min_x1, vector<int> min_x2, vector<int> lock_arr, int n, int n1) {
  int i,j;
  //print min_x1 first
  bool pass_min_x1[n1]={};
  for(i=0;i<n;i++) {
    for(j=0;j<n1;j++) {
      if(pass_min_x1[j]==false) {
        if(lock_arr[i]==min_x1[j]) {
          pass_min_x1[j]=true;
          cout << min_x1[j] << " ";
        }
      }
    }
  }
  cout << "\n";
  bool pass_min_x2[n-n1]={};
  for(i=0;i<n;i++) {
    for(j=0;j<n-n1;j++) {
      if(pass_min_x2[j]==false) {
        if(lock_arr[i]==min_x2[j]) {
          pass_min_x2[j]=true;
          cout << min_x2[j] << " ";
        }
      }
    }
  }
}
int main() 
{
    int n,i,j,n1,dif,min_dif;
    bool stop;
    cin >> n;
    if(n%2==0) {
      n1=n/2;
    }
    else if(n%2==1) {
      n1=(n-1)/2;
    }
    vector<int> x1(n1),x2(n-n1),arr(n),lock_arr(n);
    vector<int> min_x1(n1),min_x2(n-n1);
    for(i=0;i<n;i++) {
      cin >> arr[i];
      lock_arr[i]=arr[i];
    }
    sort(arr.begin(),arr.end());
    //begin setup 2 sets
    int ix1=0,ix2=0;
    for(i=0;i<n;i++) {
      //store in x1
      if(i%2==0) {
        x2[ix2]=arr[i];
        ix2++;
      }
      //store in x2
      else if(i%2==1) {
        x1[ix1]=arr[i];
        ix1++;
      }
    }
    dif=test(x1,x2,n,n1);
    min_dif=abs(dif);
    copy(min_x1,min_x2,x1,x2,n,n1);
    //now slowly repair
  int l;stop=false;
  for(l=0;l<=n;l++) {
    for(i=0;i<n1;i++) {
      for(j=0;j<n-n1;j++) {
        if(dif>0) {
          if(x1[i]>x2[j]) {
            swap(x1[i],x2[j]);
          }
        }
        else if(dif<0) {
          if(x1[i]<x2[j]) {
            swap(x1[i],x2[j]);
          }
        }
        if(min_dif==0) {
          stop=true;break;
        }
        dif=test(x1,x2,n,n1);
        if(abs(dif)<=abs(min_dif)) {
          min_dif=abs(dif);
          copy(min_x1,min_x2,x1,x2,n,n1);
        }
      }
      if(stop==true) {break;}
    }
  }
  //show(min_x1,min_x2,lock_arr,n,n1);cout << "\n";
  //debug
    //swap first setup
    for(i=0;i<n1;i++) {
      swap(x1[i],x2[i]);
    }
    //find min again
  stop=true;
  for(l=0;l<=n;l++) {
    for(i=0;i<n1;i++) {
      for(j=0;j<n-n1;j++) {
        if(dif>0) {
          if(x1[i]>x2[j]) {
            swap(x1[i],x2[j]);
          }
        }
        else if(dif<0) {
          if(x1[i]<x2[j]) {
            swap(x1[i],x2[j]);
          }
        }
        if(min_dif==0) {
          stop=true;break;
        }
        dif=test(x1,x2,n,n1);
        if(abs(dif)<=abs(min_dif)) {
          min_dif=abs(dif);
          copy(min_x1,min_x2,x1,x2,n,n1);
        }
      }
      if(stop==true) {break;}
    }
  }
  /*//debug
    cout << "\n--\n";
    for(i=0;i<n1;i++) {
      cout << min_x1[i] << " ";
    }
    cout << "\n";
    for(i=0;i<n-n1;i++) {
      cout << min_x2[i] << " ";
    }
    cout << "\n\n";*/
    show(min_x1,min_x2,lock_arr,n,n1);
    return 0;
    
}