1472E.md (3044B)
1 Source: https://codeforces.com/problemset/problem/1472/E 2 3 E. Correct Placement 4 5 time limit per test 6 7 4 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Polycarp has invited $n$ friends to celebrate the New Year. During the celebration, he decided to take a group photo of all his friends. Each friend can stand or lie on the side. 22 23 Each friend is characterized by two values $h_i$ (their height) and $w_i$ (their width). On the photo the $i$-th friend will occupy a rectangle $h_i \times w_i$ (if they are standing) or $w_i \times h_i$ (if they are lying on the side). 24 25 The $j$-th friend can be placed in front of the $i$-th friend on the photo if his rectangle is lower and narrower than the rectangle of the $i$-th friend. Formally, at least one of the following conditions must be fulfilled: 26 27 * $h_j \lt h_i$ and $w_j \lt w_i$ (both friends are standing or both are lying); 28 * $w_j \lt h_i$ and $h_j \lt w_i$ (one of the friends is standing and the other is lying). 29 30 For example, if $n = 3$, $h=[3,5,3]$ and $w=[4,4,3]$, then: 31 32 * the first friend can be placed in front of the second: $w_1 \lt h_2$ and $h_1 \lt w_2$ (one of the them is standing and the other one is lying); 33 * the third friend can be placed in front of the second: $h_3 \lt h_2$ and $w_3 \lt w_2$ (both friends are standing or both are lying). 34 35 In other cases, the person in the foreground will overlap the person in the background. 36 37 Help Polycarp for each $i$ find any $j$, such that the $j$-th friend can be located in front of the $i$-th friend (i.e. at least one of the conditions above is fulfilled). 38 39 Please note that you do not need to find the arrangement of all people for a group photo. You just need to find for each friend $i$ any other friend $j$ who can be located in front of him. Think about it as you need to solve $n$ separate independent subproblems. 40 41 Input 42 43 The first line contains one integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. Then $t$ test cases follow. 44 45 The first line of each test case contains one integer $n$ ($1 \leq n \leq 2 \cdot 10^5$) — the number of friends. 46 47 This is followed by $n$ lines, each of which contains a description of the corresponding friend. Each friend is described by two integers $h_i$ and $w_i$ ($1 \leq h_i, w_i \leq 10^9$) — height and width of the $i$-th friend, respectively. 48 49 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. 50 51 Output 52 53 For each test case output $n$ integers on a separate line, where the $i$-th number is the index of a friend that can be placed in front of the $i$-th. If there is no such friend, then output -1. 54 55 If there are several answers, output any. 56 57 Example 58 59 Input 60 61 ``` 62 4 63 3 64 3 4 65 5 4 66 3 3 67 3 68 1 3 69 2 2 70 3 1 71 4 72 2 2 73 3 1 74 6 3 75 5 4 76 4 77 2 2 78 2 3 79 1 1 80 4 4 81 ``` 82 83 Output 84 85 ``` 86 -1 3 -1 87 -1 -1 -1 88 -1 -1 2 2 89 3 3 -1 3 90 ``` 91 92 Note 93 94 The first test case is described in the statement. 95 96 In the third test case, the following answers are also correct: 97 98 * $[-1, -1, 1, 2]$; 99 * $[-1, -1, 1, 1]$; 100 * $[-1, -1, 2, 1]$.