problem.txt (4516B)
1 D. Portal 2 Finished 3 Practice 4 time limit per test: 2 seconds 5 memory limit per test: 256 megabytes 6 You are given a permutation∗ p of length n . There are also two portals located at positions x 7 and y (x < y). 8 A portal at position i is initially located between the i -th and (i + 1) -th elements of the array. 9 Specifically, if i = 0, then the portal is located before the first element of the array, and if 10 i = n , then the portal is located after the last element. 11 You may perform either of the following two operations as many times as you like: 12 1. Remove the element to the immediate left of one portal and insert it to the immediate right 13 of the other portal. 14 2. Remove the element to the immediate right of one portal and insert it to the immediate left 15 of the other portal. 16 Let O denote a portal. For example, if p is [3, O, 2, 4, O, 1]: 17 → Virtual participation 18 19 Virtual contest is a way to take part in past contest, 20 as close as possible to participation on time. It is 21 supported only ICPC mode for virtual contests. If 22 you've seen these problems, a virtual contest is not 23 for you - solve these problems in the archive. If you 24 just want to solve some problem from a contest, a 25 virtual contest is not for you - solve this problem in 26 the archive. Never use someone else's code, read 27 the tutorials or communicate with other person 28 during a virtual contest. 29 Start virtual contest 30 → Clone Contest to Mashup 31 • Using operation 1 on the left and right portals respectively results in the arrays 32 [O, 2, 4, O, 3, 1] and [3, O, 4, 2, O, 1]. 33 34 You can clone this contest to a mashup. 35 Clone Contest 36 • Using operation 2 on the left and right portals respectively results in the arrays 37 [3, O, 4, 2, O, 1] and [3, 1, O, 2, 4, O]. 38 Find the lexicographically† smallest permutation you can obtain using these operations. Note 39 that portals do not affect the lexicographical comparison of permutations. 40 ∗A permutation of length n is an array of length n containing each integer from 1 to n exactly once. 41 †A permutation a is lexicographically smaller than permutation b if there exists an index i such that aj = bj 42 for all indices 1 ≤ j < i and ai < bi . 43 → Submit? 44 Language:GNU G++23 14.2 (64 bit, msys2) 45 Choose 46 file:Browse… No file selected. 47 Input 48 The first line contains an integer t (1 ≤ t ≤ 2 ⋅ 104 ) — the number of test cases. 49 For each test case, the first line contains three integers n , x , and y (1 ≤ n ≤ 2 ⋅ 105 , 50 0 ≤ x < y ≤ n). 51 The second line of each test case contains n integers p1 , p2 , … , pn — a permutation of 52 length n . 53 The sum of n over all test cases does not exceed 2 ⋅ 105 . 54 Submit 55 Output 56 For each test case, output a line with n integers — the lexicographically smallest permutation 57 you can obtain. 58 59 --- 60 61 thoughts: 62 63 - given a permutation p of length n 64 - there are two portals at positions x and y s.t. x < y 65 - a portal i is between the ith and ith + 1 elements 66 - at end, append 67 - do the either of the following as many times as you'd like (I think we can jump between them over time) 68 - remove element to the left of a portal and put it to the right of the other portal 69 - remove the element to the right of a portal and put it to the left of the other portal 70 - find the smallest lexicographically permutation using only these ops 71 72 --- 73 74 example: 75 76 4 0 4 77 3 1 4 2 78 79 n = 4 80 x = 0 81 y = 4 82 83 p 3 1 4 2 p 84 85 what do ops do? 86 87 - are there just two seperate sets that are disjoint, the sets that are on each side of a portal, can they get to the other side? 88 89 1 4 2 3 90 91 p 1 4 2 3 p 92 93 I guess this is just one swap, moving the 3 -> p -> left of p2 94 95 --- 96 97 3 1 2 98 3 2 1 99 100 3 p 2 p 1 101 102 3 -> p -> end - 1 103 104 p 2 p 3 1 105 106 okay, so is this just about sorting the two smaller groupings, it does seem that there's no group movement possible. 107 108 --- 109 idea: while swapping to the other side results in a smaller lefmost character then swap them? how? 110 111 --- 112 113 5 1 3 114 1 3 5 2 4 115 116 1 p 3 5 p 2 4 117 118 (that's pretty bad bc that moves the rightmost to being 3) 119 120 p 3 5 p 1 2 4 121 122 don't do that 123 124 1 p 3 5 p 2 4 125 126 1 2 p 3 5 p 4 127 128 1 2 3 5 4 129 130 --- 131 132 2 0 1 133 1 2 134 135 136 p 1 p 2 137 138 this is good as is 139 140 i guess we can do a two pointer-based comparison. 141 142 like what we'd do is this: 143 144 - should we move elements on the right of p2 to the left of p1? 145 - if the current element is smaller than the element to the right of portal, yes 146 - should we move elements on the left of p1 to the right of p2 147 - if the element on the right of p is smaller than the element on the left then yes 148 - do we have to consider the other cases?