1998B.md (1887B)
1 Source: https://codeforces.com/problemset/problem/1998/B 2 3 B. Minimize Equal Sum Subarrays 4 5 time limit per test 6 7 1.5 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 It is known that [Farmer John likes Permutations](https://usaco.org/index.php?page=viewproblem2&cpid=1421), but I like them too! 22 23 — Sun Tzu, The Art of Constructing Permutations 24 25 You are given a permutation$^{\text{∗}}$ $p$ of length $n$. 26 27 Find a permutation $q$ of length $n$ that minimizes the number of pairs ($i, j$) ($1 \leq i \leq j \leq n$) such that $p_i + p_{i+1} + \ldots + p_j = q_i + q_{i+1} + \ldots + q_j$. 28 29 $^{\text{∗}}$A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array). 30 31 Input 32 33 The first line contains $t$ ($1 \leq t \leq 10^4$) — the number of test cases. 34 35 The first line of each test case contains $n$ ($1 \leq n \leq 2 \cdot 10^5$). 36 37 The following line contains $n$ space-separated integers $p_1, p_2, \ldots, p_n$ ($1 \leq p_i \leq n$) — denoting the permutation $p$ of length $n$. 38 39 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. 40 41 Output 42 43 For each test case, output one line containing any permutation of length $n$ (the permutation $q$) such that $q$ minimizes the number of pairs. 44 45 Example 46 47 Input 48 49 ``` 50 3 51 52 2 53 54 1 2 55 56 5 57 58 1 2 3 4 5 59 60 7 61 62 4 7 5 1 2 6 3 63 ``` 64 65 Output 66 67 ``` 68 2 1 69 3 5 4 2 1 70 6 2 1 4 7 3 5 71 ``` 72 73 Note 74 75 For the first test, there exists only one pair ($i, j$) ($1 \leq i \leq j \leq n$) such that $p_i + p_{i+1} + \ldots + p_j = q_i + q_{i+1} + \ldots + q_j$, which is ($1, 2$). It can be proven that no such $q$ exists for which there are no pairs.