codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1978C.md (2539B)


      1 Source: https://codeforces.com/problemset/problem/1978/C
      2 
      3 C. Manhattan Permutations
      4 
      5 time limit per test
      6 
      7 2 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 Let's call the Manhattan value of a permutation$^{\dagger}$ $p$ the value of the expression $|p_1 - 1| + |p_2 - 2| + \ldots + |p_n - n|$.
     22 
     23 For example, for the permutation $[1, 2, 3]$, the Manhattan value is $|1 - 1| + |2 - 2| + |3 - 3| = 0$, and for the permutation $[3, 1, 2]$, the Manhattan value is $|3 - 1| + |1 - 2| + |2 - 3| = 2 + 1 + 1 = 4$.
     24 
     25 You are given integers $n$ and $k$. Find a permutation $p$ of length $n$ such that its Manhattan value is equal to $k$, or determine that no such permutation exists.
     26 
     27 $^{\dagger}$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).
     28 
     29 Input
     30 
     31 Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 10^{4}$) — the number of test cases. The description of the test cases follows.
     32 
     33 The only line of each test case contains two integers $n$ and $k$ ($1 \le n \le 2 \cdot 10^{5}, 0 \le k \le 10^{12}$) — the length of the permutation and the required Manhattan value.
     34 
     35 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^{5}$.
     36 
     37 Output
     38 
     39 For each test case, if there is no suitable permutation, output "No". Otherwise, in the first line, output "Yes", and in the second line, output $n$ distinct integers $p_1, p_2, \ldots, p_n$ ($1 \le p_i \le n$) — a suitable permutation.
     40 
     41 If there are multiple solutions, output any of them.
     42 
     43 You can output the answer in any case (for example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as a positive answer).
     44 
     45 Example
     46 
     47 Input
     48 
     49 ```
     50 8
     51 
     52 3 4
     53 
     54 4 5
     55 
     56 7 0
     57 
     58 1 1000000000000
     59 
     60 8 14
     61 
     62 112 777
     63 
     64 5 12
     65 
     66 5 2
     67 ```
     68 
     69 Output
     70 
     71 ```
     72 Yes
     73 3 1 2
     74 No
     75 Yes
     76 1 2 3 4 5 6 7
     77 No
     78 Yes
     79 8 2 3 4 5 6 1 7
     80 No
     81 Yes
     82 5 4 3 1 2
     83 Yes
     84 2 1 3 4 5
     85 ```
     86 
     87 Note
     88 
     89 In the first test case, the permutation $[3, 1, 2]$ is suitable, its Manhattan value is $|3 - 1| + |1 - 2| + |2 - 3| = 2 + 1 + 1 = 4$.
     90 
     91 In the second test case, it can be proven that there is no permutation of length $4$ with a Manhattan value of $5$.
     92 
     93 In the third test case, the permutation $[1,2,3,4,5,6,7]$ is suitable, its Manhattan value is $|1-1|+|2-2|+|3-3|+|4-4|+|5-5|+|6-6|+|7-7|=0$.