codeforces-scrape

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

2078B.md (2532B)


      1 Source: https://codeforces.com/problemset/problem/2078/B
      2 
      3 B. Vicious Labyrinth
      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 [Axium Crisis - ak+q](https://youtu.be/1HyuI8Bvnsg?si=6amlU5OPKnJiydZs)
     22 
     23 There are $n$ cells in a labyrinth, and cell $i$ ($1 \leq i \leq n$) is $n - i$ kilometers away from the exit. In particular, cell $n$ is the exit. Note also that each cell is connected to the exit but is not accessible from any other cell in any way.
     24 
     25 In each cell, there is initially exactly one person stuck in it. You want to help everyone get as close to the exit as possible by installing a teleporter in each cell $i$ ($1 \leq i \leq n$), which translocates the person in that cell to another cell $a_i$.
     26 
     27 The labyrinth owner caught you in the act. Amused, she let you continue, but under some conditions:
     28 
     29 * Everyone must use the teleporter exactly $k$ times.
     30 * No teleporter in any cell can lead to the same cell it is in. Formally, $i \neq a_i$ for all $1 \leq i \leq n$.
     31 
     32 You must find a teleporter configuration that minimizes the sum of distances of all individuals from the exit after using the teleporter exactly $k$ times while still satisfying the restrictions of the labyrinth owner.
     33 
     34 If there are many possible configurations, you can output any of them.
     35 
     36 Input
     37 
     38 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.
     39 
     40 The first and only line of each test case contains two integers $n$ and $k$ ($2 \leq n \leq 2 \cdot 10^5$, $1 \leq k \leq 10^9$) — the number of cells in the labyrinth and the value $k$.
     41 
     42 It is guaranteed that the total sum of $n$ across all test cases does not exceed $2 \cdot 10^5$.
     43 
     44 Output
     45 
     46 For each test case, output $n$ integers — the destinations of the teleporters $a_1, a_2, \ldots, a_n$ in order, satisfying the given conditions ($1 \leq a_i \leq n$, $a_i \neq i$).
     47 
     48 Example
     49 
     50 Input
     51 
     52 ```
     53 2
     54 
     55 2 1
     56 
     57 3 2
     58 ```
     59 
     60 Output
     61 
     62 ```
     63 2 1
     64 
     65 2 3 2
     66 ```
     67 
     68 Note
     69 
     70 In the first test case, the position of each person is as follows.
     71 
     72 * Before teleporting: $[1, 2]$.
     73 * First teleportation: $[2, 1]$.
     74 
     75 The distance sum is $(2-2) + (2-1) = 1$, which is the minimum possible.
     76 
     77 In the second test case, the position of each person is as follows.
     78 
     79 * Before teleporting: $[1, 2, 3]$.
     80 * First teleportation: $[2, 3, 2]$.
     81 * Second teleportation: $[3, 2, 3]$.
     82 
     83 The distance sum is $(3-3) + (3-2) + (3-3) = 1$, which is the minimum possible.