题面#

qwqkawaii is registering for $n$ ($n\le 50$) courses. In the registration system, he can submit a course wish for each course, which indicates his priority for taking that course.

Course wishes are divided into $k+1$ ($k\le 20$) priority levels, where level $1$ is the highest priority and level $k+1$ is the lowest.

The first $k$ wish levels have capacity limits: for each $1 \le i \le k$, at most $a_i$ courses can be assigned wish level $i$. Note that wish level $k+1$ has no capacity limit.

Initially, the $i$-th course has wish level $b_i$, and it is guaranteed that this initial assignment satisfies all capacity limits. Now qwqkawaii wants to adjust all his courses to wish level $k + 1$. To achieve this, he can apply the following operation at most $1000$ times:

• Select a course $i$ ($1\le i\le n$), then increase $b_i$ by $1$.

Note that:

• A course at level $k+1$ cannot be selected;
• After every single operation, all capacity limits must still be satisfied.

Your task is to construct a valid adjustment sequence with at most $1000$ operations, or report that it is impossible.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 50$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $k$ ($1 \le n \le 50$, $1 \le k \le 20$) — the number of courses and the number of priority levels (excluding the lowest priority level).

The second line contains $k$ integers $a_1, a_2, \ldots, a_k$ ($1 \le a_i \le n$) — the capacity limits of the first $k$ wish levels.

The third line contains $n$ integers $b_1, b_2, \ldots, b_n$ ($1 \le b_i \le k+1$) — the initial wish levels of the courses.

It is guaranteed that the initial assignment satisfies all capacity limits.

Output

For each test case, if it is impossible to reach the target state, print a single integer $-1$.

Otherwise, print the number of operations $m$ ($0 \le m \le 1000$) on the first line of output.

Then print one line with $m$ integers $u_1, u_2, \ldots, u_m$ ($1 \le u_i \le n$), denoting that in the $i$-th operation, you increase the wish level $b_{u_i}$ of course $u_i$ by $1$.

思路#

题目要求构造一种操作顺序，把所有课程从当前等级逐步提升到 $k+1$，并且每一步后都不能违反容量限制

考虑贪心：每次都从当前“最高的非空等级”中取一门课上移

设当前最高非空等级为 $x$（$1 \le x \le k$），把一门课从 $x$ 移到 $x+1$：

• $x$ 层人数减少，一定不会超容量
• 由于 $x$ 已经是当前最高层，所以 $x+1..k$ 都为空，特别是 $x+1$ 层原本为 $0$
• 移动后 $x+1$ 层最多变成 $1$，而题目给出 $a_i \ge 1$，因此也合法
• 若 $x=k$，则进入 $k+1$（无容量限制），同样合法

因此这个过程一定可以持续进行，直到 $1..k$ 全部为空，此时所有课程都在 $k+1$

总操作数是固定的：

由约束 $n \le 50, k \le 20$，有 $m \le 50 \times 20 = 1000$，满足题目要求

实现时可用 levels[1..k+1] 存每个等级的课程编号，每轮从 $k$ 向 $1$ 找最高非空层并执行一次移动，记录课程编号到答案即可。复杂度为 $O(mk)$

代码#

1
#include <bits/stdc++.h>
2

3
using namespace std;
4

5
int main() {
6
    ios::sync_with_stdio(false);
7
    cin.tie(nullptr);
8

9
    int t;
10
    cin >> t;
11
    while (t--) {
12
        int n, k;
13
        cin >> n >> k;
14

15
        vector<int> a(k + 1), b(n + 1);
16
        for (int i = 1; i <= k; i++) cin >> a[i];
17
        for (int i = 1; i <= n; i++) cin >> b[i];
18

19
        vector<vector<int>> levels(k + 2);
20
        vector<int> cnt(k + 2, 0);
21

22
        for (int i = 1; i <= n; i++) {
23
            levels[b[i]].push_back(i);
24
            if (b[i] <= k) cnt[b[i]]++;
25
        }
26

27
        vector<int> ans;
28
        ans.reserve(1000);
29

30
        bool fail = false;
31

32
        while (true) {
33
            int x = 0;
34
            for (int lv = k; lv >= 1; lv--) {
35
                if (!levels[lv].empty()) {
36
                    x = lv;
37
                    break;
38
                }
39
            }
40

41
            if (x == 0) break;
42

43
            if (x < k && cnt[x + 1] + 1 > a[x + 1]) {
44
                fail = true;
45
                break;
46
            }
47

48
            int id = levels[x].back();
49
            levels[x].pop_back();
50

51
            ans.push_back(id);
52

53
            cnt[x]--;
54
            if (x + 1 <= k) cnt[x + 1]++;
55

56
            levels[x + 1].push_back(id);
57

58
            if ((int)ans.size() > 1000) {
59
                fail = true;
60
                break;
61
            }
62
        }
63

64
        if (fail) {
65
            cout << -1 << '\n';
66
            continue;
67
        }
68

69
        cout << ans.size() << '\n';
70
        for (int i = 0; i < (int)ans.size(); i++) {
71
            if (i) cout << ' ';
72
            cout << ans[i];
73
        }
74
        cout << '\n';
75
    }
76

77
    return 0;
78
}