放放/ll/ll/ll。
这题是个性质题。
首先第一排一定是升序，第二排一定是降序。考虑第一排若存在 \(i < j\) 使得 \(a_{1, i} > a_{1, j}\)，那么交换这两个数不会变劣。第二排类似。
然后发现在 \(1\) 走下去或在 \(n\) 走下去最优。考虑先求出从 \(1\) 走下去的答案 \(k\)，然后令 \(w_i = a_{1, i + 1} - a_{2, i}\)，那么从位置 \(x\) 走下去的答案就是 \(k + \sum\limits_{i = 1}^{x - 1} w_i\)。容易发现 \(w_i\) 单增，所以只可能在 \(1\) 或 \(n\) 处取到最值。
最后发现 \(a_{1, 1}, a_{2, n}\) 一定是最小值或次小值。若不是则把最小值（或次小值）交换过去不会变劣。
然后直接写个背包 dp，bitset 优化一下就完了。
时间复杂度 \(O(n^2 \sum a) = O(n^3 \max a)\)。
code
// Problem: E. Turtle
// Contest: Codeforces - Codeforces Round 594 (Div. 1)
// URL: https://codeforces.com/problemset/problem/1239/E
// Memory Limit: 512 MB
// Time Limit: 5000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 27;
int n, a[maxn << 1], b[2][maxn];
bitset<maxn * 50000> f[maxn << 1][maxn];
void solve() {
scanf("%d", &n);
for (int i = 1; i <= n * 2; ++i) {
scanf("%d", &a[i]);
}
sort(a + 1, a + n * 2 + 1);
b[0][1] = a[1];
b[1][n] = a[2];
f[2][0].set(0);
int s = 0;
for (int i = 3; i <= n * 2; ++i) {
s += a[i];
for (int j = 0; j <= i - 2; ++j) {
f[i][j] = f[i - 1][j];
if (j) {
f[i][j] |= (f[i - 1][j - 1] << a[i]);
}
}
}
vector<int> A, B;
int p = -1;
for (int i = s / 2; ~i; --i) {
if (f[n * 2][n - 1].test(i)) {
p = i;
break;
}
}
for (int i = n * 2, j = n - 1; i >= 3; --i) {
if (p >= a[i] && j && f[i - 1][j - 1].test(p - a[i])) {
--j;
A.pb(a[i]);
p -= a[i];
} else {
B.pb(a[i]);
}
}
sort(A.begin(), A.end());
for (int i = 2; i <= n; ++i) {
b[0][i] = A[i - 2];
}
sort(B.begin(), B.end(), greater<int>());
for (int i = 1; i < n; ++i) {
b[1][i] = B[i - 1];
}
for (int i = 0; i < 2; ++i) {
for (int j = 1; j <= n; ++j) {
printf("%d ", b[i][j]);
}
putchar('\n');
}
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}