Merge Not Sort

发表于 分类于 ，

    已知对两个长度为 $N$ 的、可能未排序的数组 $A$ 和 $B$ 执行如下的归并操作，生成的数组是一个长度为 $2N$ 的、给定的排列（即 $[1,2N]$ 中每个整数都正好出现一遍的数组）$C$：

    ```

    Merge(A[1..N], B[1..N]):

    C = []

    i = 1

    j = 1

    while i <= N AND j <= N:

    if A[i] &lt; B[j]:  append A[i] to C  i = i + 1else:  append B[j] to C  j = j + 1

    while i <= N:

    append A[i] to Ci = i + 1

    while j <= N:

    append B[j] to Cj = j + 1

    return C

    ```

    构造出任意一组符合条件的 $A,B$；如果无解输出 -1。

    翻译自 @zyc212303。

Merge Not Sort

Created by LXC on Wed May 8 15:52:43 2024

https://codeforces.com/problemset/problem/1906/E

ranting: 1900

tag: constructive algorithms, dp

problem

已知对两个长度为 $N$ 的、可能未排序的数组 $A$ 和 $B$ 执行如下的归并操作，生成的数组是一个长度为 $2N$ 的、给定的排列（即 $[1,2N]$ 中每个整数都正好出现一遍的数组）$C$：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Merge(A[1..N], B[1..N]):
  C = []
  i = 1
  j = 1
  while i <= N AND j <= N:
    if A[i] < B[j]:
      append A[i] to C
      i = i + 1
    else:
      append B[j] to C
      j = j + 1 
  while i <= N:
    append A[i] to C
    i = i + 1 
  while j <= N:
    append B[j] to C
    j = j + 1 
  return C

构造出任意一组符合条件的 $A,B$；如果无解输出 -1。

翻译自 @zyc212303。

solution

观察$C_1>C_2$那么$C_1$和$C_2$必须在同一个数组中，进一步观察发现我们找到最小的i，使得$C_1 < C_i$，那么$C_1, C_2, \cdots, C_{i-1}$也需要在同一个数组中。

我们需要将$C$数组分成多段，每一段的第一个数严格大于这一段中其他数。不妨分成了m段，每一段的大小分别是$sz_1, sz_2, \cdots, sz_m$

现在问题就变为了从m个数中选出若干个数使得总和等于n。可以用01背包解决。

然后逆向构造，得到一个数组选了哪些段，另一个数组就是剩下的段。

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

random_device seed;
ranlux48 engine(seed());
int random(int l, int r) {
    uniform_int_distribution<> distrib(l, r);
    return distrib(engine);
}
template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p) {
    return os<<'['<<p.first<<", "<<p.second<<']';
}
template<class t> ostream& operator<<(ostream& os,const vector<t>& v) {
    os<<'['; int s = 1;
    for(auto e:v) { if (s) s = 0; else os << ", "; os << e; }
    return os<<']';
}
template<class t,class u> ostream& operator<<(ostream& os,const map<t,u>& mp){
    os<<'{'; int s = 1;
    for(auto [x,y]:mp) { if (s) s = 0; else os << ", "; os<<x<<": "<<y; }
    return os<<'}';
}

void sol() {
    int n;
    cin >> n;
    vector<int> c(2*n);
    for (auto& i:c) cin >> i;
    vector<vector<int>> g;
    for (int i=0; i<2*n;) {
        int j = i+1;
        while (j<2*n && c[i] > c[j]) j++;
        vector<int> t;
        while (i<j) {
            t.push_back(c[i]);
            i++;
        }
        g.emplace_back(t);
    }
    // cout << g << endl;
    int sz = g.size();
    vector<vector<int>> f(sz, vector<int>(n+1, -1));
    // f[i][j] = f[i-1][j] or f[i-1][j-g[i].size()]
    function<int(int,int)> dfs = [&](int i, int j)->int {
        if (i == -1) return j == 0;
        if (f[i][j] != -1) return f[i][j];
        f[i][j] = dfs(i-1, j);
        if (j>=g[i].size()) f[i][j] |= dfs(i-1, j-g[i].size());
        return f[i][j];
    };
    // for (int i=0; i<sz; i++) {
    //     for (int j=0; j<=n; j++) {
    //         cout << i << " " << j << " = " << dfs(i,j) << endl;
    //     }
    // }
    if (dfs(sz-1, n) == 0) {
        cout << "-1\n";
        return ;
    }
    vector<int> p;
    for (int i=sz-1, j=n; i>=0; i--) {
        if (dfs(i-1,j)) continue;
        j -= g[i].size();
        p.push_back(i);
    }
    reverse(p.begin(), p.end());
    // cout << p << endl;
    vector<int> a, b;
    int idx = 0;
    for (int i=0; i<sz; i++) {
        if (idx<p.size() && p[idx] == i) {
            for (int j:g[i]) a.push_back(j);
            idx++;
        } else {
            for (int j:g[i]) b.push_back(j);
        }
    }
    // cout << a << endl;
    // cout << b << endl;
    // if (a.size() != b.size()) {
    //     cout << a.size() << " " << b.size() << endl;
    //     assert(0);
    // }
    for (int i:a) cout << i << " "; cout << "\n";
    for (int i:b) cout << i << " "; cout << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}