CF1472E Correct Placement

Polycarp 邀请了 $n$ 位朋友一起庆祝新年。在庆祝活动中，他决定为所有朋友拍一张合影。每位朋友可以选择站立或侧躺。 每位朋友有两个属性 $h_i$（身高）和 $w_i$（宽度）。在照片上，第 $i$ 位朋友占据一个 $h_i \times w_i$ 的矩形（如果他站立）或 $w_i \times h_i$ 的矩形（如果他侧躺）。 如果第 $j$ 位朋友的矩形比第 $i$ 位朋友的矩形更矮且更窄，则第 $j$ 位朋友可以站在第 $i$ 位朋友的前面。具体来说，满足下列至少一个条件即可： - $h_j < h_i$ 且 $w_j < w_i$（两人都站立或都侧躺）； - $w_j < h_i$ 且 $h_j < w_i$（其中一人站立，另一人侧躺）。 例如，如果 $n = 3$，$h=[3,5,3]$，$w=[4,4,3]$，那么： - 第一位朋友可以站在第二位朋友前面：$w_1 < h_2$ 且 $h_1 < w_2$（一人站立，另一人侧躺）； - 第三位朋友可以站在第二位朋友前面：$h_3 < h_2$ 且 $w_3 < w_2$（两人都站立或都侧躺）。 其他情况下，前排的人会遮挡住后排的人。 请帮助 Polycarp，对于每个 $i$，找到任意一个 $j$，使得第 $j$ 位朋友可以站在第 $i$ 位朋友前面（即至少满足上述条件之一）。 请注意，你不需要为合影找到所有人的排列顺序。你只需要为每个朋友 $i$ 找到任意一个可以站在他前面的朋友 $j$。可以将其看作是 $n$ 个独立的子问题。

第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的数量。接下来是 $t$ 组测试数据。 每组测试数据的第一行包含一个整数 $n$（$1 \leq n \leq 2 \times 10^5$），表示朋友的数量。 接下来的 $n$ 行，每行包含两个整数 $h_i$ 和 $w_i$（$1 \leq h_i, w_i \leq 10^9$），分别表示第 $i$ 位朋友的身高和宽度。 保证所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$。

对于每个测试用例，输出 $n$ 个整数，单独占一行，第 $i$ 个数表示可以站在第 $i$ 位朋友前面的朋友的编号。如果不存在这样的朋友，则输出 $-1$。 如果有多个答案，输出任意一个即可。

第一个测试用例在题目描述中已经给出。 在第三个测试用例中，以下答案也是正确的： - $[-1, -1, 1, 2]$； - $[-1, -1, 1, 1]$； - $[-1, -1, 2, 1]$。 由 ChatGPT 4.1 翻译