由于左上角和右下角必须经过，所以可以直接把最小的两个数放在左上角和右下角。

考虑交换第一行的两个左大右小的相邻的数对答案产生的影响，显然，这只会使路径上数的总和的最大值变小或不变。第二行同理。于是我们得到了如下结论：第一行的数从小到大排是最优的，第二行的数从大到小排是最优的。

由于第一行 $a_{1,i}$ 递增，第二行 $a_{2,i}$ 递减，所以 $a_{1,i+1}-a_{2,i}$（可能为负）递增，所以随着拐点从左向右移动，路径上数的总和先变小再变大，所以最大权值的路径必定是在第一格向下或在最后一格向下，权值为第一行后 $n-1$ 格总和与第二行前 $n-1$ 格总和中的较大值。由于总和不变，所以我们希望两个和尽可能接近总和的一半。

令 $f(i,j,k)$ 表示能否从前 $i$ 个数中选出 $j$ 个放在第一行使得它们总和为 $k$。用 bitset 优化即可。而构造方案只需要从后往前逆推即可。

时间复杂度 $\Theta\left(\dfrac{n^2\sum a}w\right)$。

/**
 * @date: 2024.01.29
 * @problem: CF1239E
 * @tags: 思维
 */

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

int n,a[51],ans[2][26];
bitset<2500001> dp[51][26];
bool vis[51];

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n*2;i++)
        scanf("%d",a+i);
    sort(a+1,a+1+2*n,[&](int x,int y){return x>y;});
    n=2*n-2;
    dp[0][0][0]=true;
    int sum=0;
    for(int i=1;i<=n;i++){
        sum+=a[i];
        dp[i][0]=dp[i-1][0];
        for(int j=min(i,n/2);j>=1;j--)
            dp[i][j]=(dp[i-1][j-1]<<a[i])|dp[i-1][j];
    }
    int minn=0x7fffffff;
    for(int i=0;i<=sum;i++)
        if(dp[n][n/2][i])minn=min(minn,max(i,sum-i));
    for(int i=n,total=n/2;i>=1;i--){
        if(dp[i-1][total][minn]);
        else vis[i]=true,minn-=a[i],total--;
    }
    n=n/2+1;
    ans[0][1]=a[2*n-1],ans[1][n]=a[2*n];
    ans[0][0]=1;
    for(int i=1;i<=2*n-2;i++)
        if(vis[i])ans[0][++ans[0][0]]=a[i];
        else ans[1][++ans[1][0]]=a[i];
    sort(ans[0]+2,ans[0]+1+n);
    sort(ans[1]+1,ans[1]+n,[&](int x,int y){return x>y;});
    for(int i=0;i<2;i++)
        for(int j=1;j<=n;j++)
            printf("%d%c",ans[i][j]," \n"[j==n]);
    return 0;
}