2093D.md (2525B)
1 Source: https://codeforces.com/problemset/problem/2093/D 2 3 D. Skibidi Table 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 Vadim loves filling square tables with integers. But today he came up with a way to do it for fun! Let's take, for example, a table of size $2 \times 2$, with rows numbered from top to bottom and columns numbered from left to right. We place $1$ in the top left cell, $2$ in the bottom right, $3$ in the bottom left, and $4$ in the top right. That's all he needs for fun! 22 23 Fortunately for Vadim, he has a table of size $2^n \times 2^n$. He plans to fill it with integers from $1$ to $2^{2n}$ in ascending order. To fill such a large table, Vadim will divide it into $4$ equal square tables, filling the top left one first, then the bottom right one, followed by the bottom left one, and finally the top right one. Each smaller table will be divided into even smaller ones as he fills them until he reaches tables of size $2 \times 2$, which he will fill in the order described above. 24 25 Now Vadim is eager to start filling the table, but he has $q$ questions of two types: 26 27 * what number will be in the cell at the $x$-th row and $y$-th column; 28 * in which cell coordinates will the number $d$ be located. 29 30 Help answer Vadim's questions. 31 32 Input 33 34 Each test consists of several sets of input data. The first line contains a single integer $t$ $(1 \leq t \leq 10)$ — the number of sets of input data. The following lines describe the input data sets. 35 36 In the first line of each data set, there is an integer $n$, describing the size of the table $(1 \le n \le 30)$. 37 38 In the second line of each data set, there is an integer $q$ — the number of questions $(1 \le q \le 20\,000)$. 39 40 In the following $q$ lines of each data set, the questions are described in the following formats: 41 42 * -> x y — What number will be in the cell $(1 \le x, y \le 2^n)$; 43 * <- d — In which cell coordinates will the number $(1 \le d \le 2^{2n})$ be located. 44 45 It is guaranteed that the sum of $q$ over all test cases does not exceed $20\,000$. 46 47 Output 48 49 Output the answers to each question on a separate line. 50 51 Example 52 53 Input 54 55 ``` 56 2 57 58 2 59 60 5 61 62 -> 4 3 63 64 <- 15 65 66 <- 4 67 68 -> 3 1 69 70 -> 1 3 71 72 1 73 74 8 75 76 -> 1 1 77 78 -> 1 2 79 80 -> 2 1 81 82 -> 2 2 83 84 <- 1 85 86 <- 2 87 88 <- 3 89 90 <- 4 91 ``` 92 93 Output 94 95 ``` 96 7 97 2 3 98 1 2 99 9 100 13 101 1 102 4 103 3 104 2 105 1 1 106 2 2 107 2 1 108 1 2 109 ``` 110 111 Note 112 113 This is how the filled table from the first example looks: 114 115 