可以做到 (O(n\log n)) 时间、(O(n)) 空间。
关键是：把可行性拆成两类条件，一类用线段树维护，另一类具有单调性，于是最后只需要尝试一次构造。
下面的做法会处理相同重量、相同价值时的原下标顺序，以及补全数值不能超过 (10^9) 的限制。题目中 Alice 取重量排序的前缀，Bob 则按价值排序、遇到装不下的物品跳过。 补全后的重量、价值都必须在 ([1,10^9]) 内。
一、把方案表示为一个前缀
记数值上限为 (M=10^9)。
把重量已知的物品按 ((w_i,i)) 升序排序，得到
$$ F_1,F_2,\ldots,F_m. $$
由于 Alice 选的是重量顺序的前缀，因此这些物品中被选中的必然是
$$ F_1,F_2,\ldots,F_k $$
这一个前缀。
对于价值未知的物品，可以统一这样填：
$$ r_i= \begin{cases} M,&i\text{ 被选中};\\ 1,&i\text{ 不被选中}. \end{cases} $$
这是安全的：让被选物品更早出现、未选物品更晚出现，只会帮助 Bob 跳过未选物品。
先处理一个特殊情况
如果 Alice 选中了一个重量为 (M) 的物品，那么必然：
$$ W=M,\qquad \text{所有物品重量都是 }M, $$
且 Alice 只选 1 号物品。
所以先检查能否把所有重量补成 (M)，并通过上述价值填法让 Bob 第一个访问 1 号物品。能够做到就直接输出。
下文只考虑所有被选物品重量都小于 (M) 的情况。
二、固定前缀后，未知重量应该怎样填？
设固定选中 (F_1,\ldots,F_k)，它们的总重量为
$$ S_k=\sum_{t=1}^{k}w_{F_t}, $$
则留给未知重量物品的重量预算是
$$ R=W-S_k. $$
设第一个未选中的已知重量物品为 (j=F_{k+1})。
为了让一个未知重量物品 (i) 排在 (j) 前面，它的重量最多为
$$ c_i(k)=\min\left(M-1,\ w_j-[i>j]\right). $$
这里 ([i>j]) 表示：若原下标 (i>j)，取 (1)，否则取 (0)。因为等重时按原下标排序，所以这个减一不能省略。
若所有已知重量物品都选中了，则令
$$ c_i(k)=M-1. $$
接下来引入分配量 (x_i)：
- (x_i>0)：选中物品 (i)，填 (w_i=x_i)；
- (x_i=0)：不选它，实际填 (w_i=M)。
因此只需要满足
$$ 0\le x_i\le c_i(k),\qquad \sum x_i\le R. $$
最优分配方式：按照这些未知重量物品在 Bob 中的顺序，依次尽量分配重量。
即每次取
$$ x_i=\min(c_i(k),\text{尚未分配的预算}). $$
这样，对于 Bob 顺序中的任意位置，排在它前面的未知重量物品总重，都达到了所有合法分配能达到的最大值。
三、把可行性拆成两个条件
考虑一个未选中的已知重量物品 (j)。
记：
$$ P_j(k)= \text{排在 }j\text{ 前面的、已选中已知重量物品的总重量}, $$
$$ C_j(k)= \sum_{\substack{i\text{ 重量未知}\\i\text{ 在 Bob 中排在 }j\text{ 前面}}} c_i(k). $$
按照刚才的贪心分配，目标选集中排在 (j) 前面的未知重量物品，总重量恰为
$$ \min(R,C_j(k)). $$
要让 Bob 跳过 (j)，需要
$$ w_j+P_j(k)+\min(R,C_j(k))>W. $$
利用 (R=W-S_k)，等价于下面两个条件同时成立：
$$ \boxed{\text{A：}\quad w_j-(S_k-P_j(k))>0} $$
$$ \boxed{\text{B：}\quad w_j+P_j(k)+C_j(k)>W} $$
未选中的未知重量物品怎么办？
它们的重量都填成了 (M)。
当 (W<M) 时，它们自然会被跳过。但 (W=M) 时，必须保证 Bob 不会在尚未选入任何物品时碰到一个应当跳过的未知重量物品。
设 (u) 是 Bob 顺序中第一个未知重量物品，只需额外满足
$$ M+P_u(k)+\min(R,c_u(k))>W. $$
当 (W=M) 时，这表示：处理完 (u) 时，已经选入了正重量。此后所有未选中的未知重量物品重量都是 (M)，一定装不下。
它也能拆成同样形式：
$$ \boxed{\text{A}_u:\quad M-(S_k-P_u(k))>0} $$
$$ \boxed{\text{B}_u:\quad M+P_u(k)+c_u(k)>W} $$
实现时，把 (u) 当成一个初始权值为 (M) 的虚拟检查点即可。这个检查点在 (W<M) 时也可以保留，因为对应条件自动成立。
四、为什么只需要尝试一个前缀？
条件 B 随着 (k) 增大是单调变容易的。
原因是：随着选中的已知重量前缀变长，剩余未选物品的 (P_j(k)) 只会增大；第一个未选中的已知重量物品向后移动，使每个 (c_i(k)) 只会增大。因此 (C_j(k)) 也只会增大。同时，需要检查的已知重量物品只会减少。
虚拟检查点也满足这个单调性。
于是，可以先找出：
$$ k^\star= \text{所有满足预算限制和条件 A 的前缀中，最大的 }k. $$
然后只对 (k^\star) 进行一次构造和验证。
证明很直接：假设某个 (k) 存在合法方案，那么它一定满足 A，所以 (k\le k^\star)；它也满足 B，而 B 单调，因此 (k^\star) 同样满足 B。故只要有解，对 (k^\star) 的贪心构造就一定成功。
注意，A 本身不要求单调，不能直接二分整个可行性。
五、线段树维护条件 A
对于每个仍未选中的已知重量物品 (j)，维护
$$ D_j=w_j-(S_k-P_j(k)). $$
其中 (S_k-P_j(k))，就是在 Bob 顺序中排在 (j) 后面的已选中已知重量物品总重。
把所有检查点按照 Bob 优先级排序。初始 (k=0)，所以普通检查点的值是 (w_j)，虚拟检查点的值是 (M)。
当一个已知重量物品 (i) 加入选中前缀时：
- 删除它自己的检查点，相当于单点赋为 (+\infty)。
- 对排在它前面的所有检查点，统一减去 (w_i)。
第二步恰好是一个前缀区间加。线段树维护区间最小值，根节点最小值大于 (0)，就表示所有 A 条件成立。
有一个实现细节：价值未知的物品，作为未选检查点时价值为 (1)，加入选集、计算更新范围时价值为 (M)。两者不能混用同一个排名。
最后对最大的合法前缀构造，模拟一次 Bob，检查是否恰好选中目标集合即可。目标集合在 Alice 的重量顺序中一定是前缀；而 Bob 跳过了所有其他物品，说明最终剩余容量装不下任何未选物品，因此 Alice 也会恰好选中该集合。
C++17 代码
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
const int64 M = 1000000000LL;
const int64 INF = (1LL << 60);
struct SegmentTree {
int n;
vector<int64> mn, lazy;
explicit SegmentTree(const vector<int64>& a)
: n((int)a.size()), mn(4 * n), lazy(4 * n, 0) {
build(1, 0, n - 1, a);
}
void build(int p, int l, int r, const vector<int64>& a) {
if (l == r) {
mn[p] = a[l];
return;
}
int mid = (l + r) / 2;
build(p * 2, l, mid, a);
build(p * 2 + 1, mid + 1, r, a);
pull(p);
}
void pull(int p) {
mn[p] = min(mn[p * 2], mn[p * 2 + 1]);
}
void apply(int p, int64 delta) {
mn[p] += delta;
lazy[p] += delta;
}
void push(int p) {
if (lazy[p] != 0) {
apply(p * 2, lazy[p]);
apply(p * 2 + 1, lazy[p]);
lazy[p] = 0;
}
}
// 给前 len 个位置加上 delta。
void addPrefix(int len, int64 delta) {
if (len > 0) addPrefix(1, 0, n - 1, len - 1, delta);
}
void addPrefix(int p, int l, int r, int last, int64 delta) {
if (r <= last) {
apply(p, delta);
return;
}
push(p);
int mid = (l + r) / 2;
addPrefix(p * 2, l, mid, last, delta);
if (last > mid) {
addPrefix(p * 2 + 1, mid + 1, r, last, delta);
}
pull(p);
}
// 已选中的固定重量物品，不再需要检查它能否被跳过。
void erase(int pos) {
erase(1, 0, n - 1, pos);
}
void erase(int p, int l, int r, int pos) {
if (l == r) {
mn[p] = INF;
lazy[p] = 0;
return;
}
push(p);
int mid = (l + r) / 2;
if (pos <= mid) erase(p * 2, l, mid, pos);
else erase(p * 2 + 1, mid + 1, r, pos);
pull(p);
}
int64 minimum() const {
return mn[1];
}
};
bool solveCase(int n, int64 W, vector<int64>& w, vector<int64>& r) {
// Alice 选中重量为 M 的物品时，唯一可能是：
// W = M，所有重量均为 M，且选中的只有 1 号物品。
if (W == M) {
bool allCanBeM = true;
int64 firstValue = (r[0] == 0 ? M : r[0]);
bool firstCanLead = true;
for (int i = 0; i < n; ++i) {
if (w[i] != 0 && w[i] != M) allCanBeM = false;
if (r[i] > firstValue) firstCanLead = false;
}
if (allCanBeM && firstCanLead) {
for (int i = 0; i < n; ++i) {
if (w[i] == 0) w[i] = M;
if (r[i] == 0) r[i] = (i == 0 ? M : 1);
}
return true;
}
}
vector<int> fixedItems, unknownItems;
for (int i = 0; i < n; ++i) {
if (w[i] != 0) fixedItems.push_back(i);
else unknownItems.push_back(i);
}
sort(fixedItems.begin(), fixedItems.end(), [&](int a, int b) {
if (w[a] != w[b]) return w[a] < w[b];
return a < b;
});
sort(unknownItems.begin(), unknownItems.end(), [&](int a, int b) {
if (r[a] != r[b]) return r[a] > r[b];
return a < b;
});
// 优先级为 (-价值, 原下标)，越小越靠前。
// 未知价值：未选中时设为 1，选中时设为 M。
vector<pair<int64, int>> keys;
for (int i : fixedItems) {
keys.emplace_back(-(r[i] == 0 ? 1 : r[i]), i);
}
// 虚拟检查点：Bob 顺序中第一个未知重量物品。
if (!unknownItems.empty()) {
int u = unknownItems[0];
keys.emplace_back(-r[u], u);
}
sort(keys.begin(), keys.end());
vector<int> pos(n, -1);
vector<int64> initial(keys.size());
for (int t = 0; t < (int)keys.size(); ++t) {
int i = keys[t].second;
pos[i] = t;
initial[t] = (w[i] == 0 ? M : w[i]);
}
SegmentTree seg(initial);
int best = 0;
int64 sum = 0, bestSum = 0;
int m = (int)fixedItems.size();
for (int k = 0; k < m; ++k) {
int i = fixedItems[k];
if (w[i] == M || sum + w[i] > W) break;
sum += w[i];
seg.erase(pos[i]);
int64 selectedValue = (r[i] == 0 ? M : r[i]);
pair<int64, int> selectedKey = {-selectedValue, i};
int len = (int)(
lower_bound(keys.begin(), keys.end(), selectedKey)
- keys.begin()
);
// 排在它前面的检查点，其“后方已选总重”增加 w[i]。
seg.addPrefix(len, -w[i]);
if (seg.minimum() > 0) {
best = k + 1;
bestSum = sum;
}
}
vector<char> chosen(n, false);
for (int k = 0; k < best; ++k) {
chosen[fixedItems[k]] = true;
}
// 按 Bob 的顺序，贪心分配未知重量物品的重量预算。
int64 budget = W - bestSum;
for (int i : unknownItems) {
int64 cap = M - 1;
if (best < m) {
// 第一个未选中的固定重量物品。
int j = fixedItems[best];
cap = min(cap, w[j] - (i > j ? 1LL : 0LL));
}
int64 take = min(budget, cap);
if (take > 0) {
w[i] = take;
budget -= take;
chosen[i] = true;
} else {
w[i] = M;
}
}
for (int i = 0; i < n; ++i) {
if (r[i] == 0) {
r[i] = (chosen[i] ? M : 1);
}
}
// Bob 若恰好选中 chosen，Alice 也一定恰好选中 chosen。
vector<int> order(n);
iota(order.begin(), order.end(), 0);
sort(order.begin(), order.end(), [&](int a, int b) {
if (r[a] != r[b]) return r[a] > r[b];
return a < b;
});
int64 remaining = W;
for (int i : order) {
bool take = (w[i] <= remaining);
if (take != (bool)chosen[i]) return false;
if (take) remaining -= w[i];
}
return true;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
int n;
int64 W;
cin >> n >> W;
vector<int64> w(n), r(n);
for (auto& x : w) cin >> x;
for (auto& x : r) cin >> x;
if (!solveCase(n, W, w, r)) {
cout << "No\n";
continue;
}
cout << "Yes\n";
for (int i = 0; i < n; ++i) {
cout << w[i] << (i + 1 == n ? '\n' : ' ');
}
for (int i = 0; i < n; ++i) {
cout << r[i] << (i + 1 == n ? '\n' : ' ');
}
}
return 0;
}排序与线段树扫描均为 (O(n\log n))，最后的构造为 (O(n))，Bob 验证包含一次 (O(n\log n)) 排序。因此总复杂度为 (O(n\log n)) 时间、(O(n)) 空间。
代码通过了题面样例；另外，将数值上限缩小后进行了 287,616 组穷举或随机暴力对拍，并在原数值上限下与枚举所有前缀的做法进行了 100,000 组随机对拍，未发现不一致。
