codeforces-scrape

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

1713.md (20248B)


      1 Source: https://codeforces.com/blog/entry/105419
      2 
      3 **Before the round starts**
      4 
      5 Great efforts have been put over last year. We want to say thanks to everybody who helped us to make this round as it is. Cannot wait to see you guys on the next one!
      6 
      7 **Testers' predictions**
      8 
      9 | Tester | A | B | C | D | E | F |
     10 | --- | --- | --- | --- | --- | --- | --- |
     11 | [tfg](/profile/tfg "Grandmaster tfg") | 800 | 1100 | 1500 | 1600 | 1900 | 2400 |
     12 | [neko_nyaaaaaaaaaaaaaaaaa](/profile/neko_nyaaaaaaaaaaaaaaaaa "Grandmaster neko_nyaaaaaaaaaaaaaaaaa") | 800 | 1100 | 1700 | 1900 | 2100 | 2600 |
     13 | [BucketPotato](/profile/BucketPotato "International Master BucketPotato") | 800 | 1000 | 1400 | 1800 | 2400 | - |
     14 | [LetterC67](/profile/LetterC67 "Master LetterC67") | 800 | 1200 | 1400 | 1600 | 2100 | - |
     15 | [FireGhost](/profile/FireGhost "Master FireGhost") | 800 | 1100 | 1500 | 1900 | 2000 | 2400 |
     16 | [fextivity](/profile/fextivity "Grandmaster fextivity") | 800 | 1000 | 1400 | 1700 | 2000 | 2400 |
     17 | [generic_placeholder_name](/profile/generic_placeholder_name "Grandmaster generic_placeholder_name") | 800 | 1100 | 1600 | 1900 | 2200 | - |
     18 
     19 **Some comments from testers and authors**
     20 
     21 **From BucketPotato**
     22 
     23 ![ ](/predownloaded/20/fe/20feac5e70d329399498c395da7a3ae258cc1e9d.png)
     24 
     25 **From tfg**
     26 
     27 ![ ](/predownloaded/81/53/815379a116da175cd0e8839e56c5a519495bade8.png)
     28 
     29 **Shower thoughts from vangtrangtan**
     30 
     31 ![ ](/predownloaded/8e/f9/8ef9c9f2d5a2ce6a488d6e7cf663e50799533ac9.png)
     32 
     33 **From Fireghost**
     34 
     35 ![ ](/predownloaded/3d/71/3d71da0f3153dcb23ab4e1a0a242d109d1f94192.png)
     36 
     37 **Also from Fireghost**
     38 
     39 ![ ](/predownloaded/a5/78/a5780471f3ddfa36fb4e9559fc52c7b3c6daf7de.png)
     40 
     41 **From thenymphsofdelphi**
     42 
     43 ![ ](/predownloaded/4a/ae/4aaec44c72989909779f5d04cefb06c60c9de57e.png)
     44 
     45 **From antontrygubO_o**
     46 
     47 ![ ](/predownloaded/c4/6c/c46c5512d8e91f3284ddbf7702d96e05339b7d85.png)
     48 
     49 **Huge help from Vladithur when polishing our statements**
     50 
     51 ![ ](/predownloaded/8d/f2/8df263200ffc7a515b053f4bcb293defaf3761a5.png) ![ ](/predownloaded/e1/d4/e1d4b1eda75582bf479f4a0f2fe1f503ae5eb667.png)
     52 
     53 **From hydroshiba**
     54 
     55 ![ ](/predownloaded/ad/71/ad71d7d3760f460aac05371d79dccdc8d2a13958.png)
     56 
     57 **From thanhchauns2**
     58 
     59 ![ ](/predownloaded/5b/bc/5bbceccd8d5f351917c3e4dd3b340762b5e864e5.png)
     60 
     61 **From me**
     62 
     63 ![ ](/predownloaded/71/e3/71e363c8386bfd3e21ead8f4adf39530c2f3ce9a.png)
     64 
     65 **From errorgorn**
     66 
     67 ![ ](/predownloaded/d7/bf/d7bf9b6fc91cd6e48d330ca6b633d051aa967889.png)
     68 
     69 [1713A - Traveling Salesman Problem](https://codeforces.com/contest/1713/problem/A)
     70 
     71 **Hint 1**
     72 
     73 Do we actually need to go off the axis?
     74 
     75 **Hint 2**
     76 
     77 How to avoid visiting an axis more than once?
     78 
     79 **Tutorial**
     80 
     81 ### [1713A - Traveling Salesman Problem](https://codeforces.com/contest/1713/problem/A)
     82 
     83 Suppose we only have boxes on the $Ox+$ axis, then the optimal strategy is going in the following way: $(0, 0), (x_{max}, 0), (0, 0)$. There is no way to do in less than $2 \cdot |x_{max}|$ moves.
     84 
     85 What if we have boxes on two axis? Let's assume it is $Oy+$, suppose we have a strategy to go in the following way: $(0, 0), (x_{max}, 0),..., (0, y_{max}), (0, 0)$. In this case it is optimal to fill the three dots with $(0, 0)$, which is just solving each axis independently.
     86 
     87 Therefore, the number of axis does not matters. For each axis that has at least one box, go from $(0, 0)$ to the farthest one, then come back to $(0, 0)$.
     88 
     89 Time complexity: $O(n)$
     90 
     91 **Solution**
     92 
     93 ```
     94 def solve():
     95     n = int(input())
     96     minX, minY, maxX, maxY = 0, 0, 0, 0
     97     for i in range(n):
     98         x, y = list(map(int, input().split()))
     99         minX = min(x, minX)
    100         maxX = max(x, maxX)
    101         minY = min(y, minY)
    102         maxY = max(y, maxY)
    103     print(2 * (maxX + maxY - minX - minY))
    104 
    105 test = int(input())
    106 while test > 0:
    107     test -= 1
    108     solve()
    109 ```
    110 
    111 **Feedback**
    112 
    113 * Didn't solve
    114 * Good problem
    115 * Average problem
    116 * Bad problem
    117 
    118 [1713B - Optimal Reduction](https://codeforces.com/contest/1713/problem/B)
    119 
    120 **Hint 1**
    121 
    122 How to calculate $f(a)$?
    123 
    124 **Hint 2**
    125 
    126 What if $a$ is intially sorted?
    127 
    128 **Hint 3**
    129 
    130 Consider $a$ has $3$ elements. What if $a_1 \gt a_2$ and $a_2 \lt a_3$?
    131 
    132 **Tutorial**
    133 
    134 ### [1713B - Optimal Reduction](https://codeforces.com/contest/1713/problem/B)
    135 
    136 Let's call $M = max(a_1, a_2, \dots, a_n)$.
    137 
    138 The problem asks us to make all its elements become $0$ in some operations. And for each operation, we subtract each elements in an subarray by $1$. Thus, every largest elements of the array have to be decreased in at least $M$ operations. And also because of that, $min(f(p))$ over all permutations $p$ of $a$ is never less than $M$.
    139 
    140 Every permutations $p$ of $a$ such that $f(p) = M$ have the same construction. That is, they can be divided into $2$ subarrays where the **left subarray** is sorted in **non-decreasing order**, and the **right subarray** is sorted in **non-increasing order**. In other words, the elements of the array should form a mountain.
    141 
    142 **Why?**
    143 
    144 This is how to perform the operations: assign $l$ equal to the index of the leftmost element whose value is not $0$, and assign $r$ equal to the index of the rightmost element whose value is also not $0$, then subtract each element $a_l, a_{l+1}, \dots, a_r$ by $1$. Repeat the operation until all elements become $0$. The thing is each element of the array is always greater or equal than every elements in the left side or the right side of it so it can never become negative at some point of performing the operations. Besides, all the largest elements are also included in each operation that we perform, which mean we've achieved the goal to make all elements of the array become $0$ in $M$ operations.
    145 
    146 So how to check whether $f(a) = M$ or not? Well, we can define $preLen$ equal to the length of the longest prefix which is sorted in non-decreasing order. Then define $sufLen$ equal to the length of the longest suffix which is sorted in non-increasing order. If $preLen + sufLen \ge n$, the answer is *YES*.
    147 
    148 Time complexity: $O(n)$
    149 
    150 **Solution**
    151 
    152 ```
    153 #include <bits/stdc++.h>
    154 using namespace std;
    155 
    156 const int N = 1e5 + 5;
    157 
    158 int n, a[N];
    159 
    160 int main() {
    161     int tc;
    162     for (cin >> tc; tc--; ) {
    163         cin >> n;
    164         for (int i = 1; i <= n; i++)
    165             cin >> a[i];
    166 
    167         int preLen = 1;
    168         while (preLen < n && a[preLen] <= a[preLen + 1])
    169             preLen++;
    170 
    171         int sufLen = 1;
    172         while (sufLen < n && a[n-sufLen] >= a[n-sufLen + 1])
    173             sufLen++;
    174 
    175         if (preLen + sufLen >= n)
    176             cout << "YES" << endl;
    177         else
    178             cout << "NO" << endl;
    179     }
    180 }
    181 ```
    182 
    183 **Feedback**
    184 
    185 * Didn't solve
    186 * Good problem
    187 * Average problem
    188 * Bad problem
    189 
    190 [1713C - Build Permutation](https://codeforces.com/contest/1713/problem/C)
    191 
    192 **Hint 1**
    193 
    194 Is there any case that the answer doesn't exist?
    195 
    196 **Hint 2**
    197 
    198 **What if:** $n \le 5$
    199 
    200 **Hint 3**
    201 
    202 Construct the suffix instead of the prefix.
    203 
    204 **Hint 4**
    205 
    206 With any positive integer $x$, there is at least one square number in $[x, 2x]$. [Proof.](https://math.stackexchange.com/questions/1190737/proving-that-there-is-a-perfect-square-between-n-and-2n)
    207 
    208 **Tutorial**
    209 
    210 ### [1713C - Build Permutation](https://codeforces.com/contest/1713/problem/C)
    211 
    212 First, let's prove that the answer always exists. Let's call the smallest square number that is not smaller than $k$ is $h$. Therefore $h \leq 2 \cdot k$, which means $h - k \leq k$. [Proof.](https://math.stackexchange.com/questions/1190737/proving-that-there-is-a-perfect-square-between-n-and-2n)
    213 
    214 So we can fill $p_i = h - i$ for $(h - k \leq i \leq k)$. Using this method we can recursively reduce $k$ to $h - k - 1$, then all the way down to $-1$.
    215 
    216 We can prove that $h - k \geq 0$, as $h \geq k$.
    217 
    218 Time complexity: $O(n)$
    219 
    220 **Solution**
    221 
    222 ```
    223 #include <bits/stdc++.h>
    224 using namespace std;
    225 
    226 const int N = 1e5 + 5;
    227 
    228 int n, ans[N];
    229 
    230 void recurse(int r) {
    231 	if (r < 0) return;
    232 	int s = sqrt(2*r); s *= s;
    233 	int l = s - r; recurse(l - 1);
    234 	for (; l <= r; l++, r--) {
    235 		ans[l] = r; ans[r] = l;
    236 	}
    237 }
    238 
    239 int main() {
    240 	int tc; cin >> tc;
    241 	while (tc--) {
    242 		cin >> n; recurse(n - 1);
    243 		for (int i = 0; i < n; i++)
    244 			cout << ans[i] << ' ';
    245 		cout << '\n';
    246 	}
    247 }
    248 ```
    249 
    250 **Feedback**
    251 
    252 * Didn't solve
    253 * Good problem
    254 * Average problem
    255 * Bad problem
    256 
    257 [1713D - Tournament Coundown](https://codeforces.com/contest/1713/problem/D)
    258 
    259 **Hint 1**
    260 
    261 We made sure that almost every $2^{n - 1}$ solutions cannot pass.
    262 
    263 **Hint 2**
    264 
    265 Did you use the $0$ query?
    266 
    267 **Hint 3**
    268 
    269 $\frac{2^{n + 1}}{3} = 2^n \cdot \frac{2}{3}$, what is the conclusion?
    270 
    271 **Tutorial**
    272 
    273 ### [1713D - Tournament Coundown](https://codeforces.com/contest/1713/problem/D)
    274 
    275 There is a way to erase $3$ participants in every $2$ queries. Since there are $2^n - 1$ participants to be removed, the number of queries will be $\left \lceil (2^n - 1) \cdot \frac{2}{3} \right \rceil = \left \lfloor \frac{2^{n + 1}}{3} \right \rfloor$. Suppose there are only $4$ participants. In the first query we will ask the judge to compare the $1^{st}$ and the $3^{rd}$ participants. There are three cases:
    276 
    277 * The $1^{st}$ participant wins more game than the $3^{rd}$ one: the $2^{nd}$ and $3^{rd}$ cannot be the winner.
    278 * The $3^{rd}$ participant wins more game than the $1^{st}$ one: the $1^{st}$ and $4^{th}$ cannot be the winner.
    279 * The $1^{st}$ and $3^{rd}$ participants' numbers of winning games are equal: both the $1^{st}$ and $3^{rd}$ cannot be the winner.
    280 
    281 Ask the remaining two participants, find the winner between them.
    282 
    283 If there are more than $4$ participants, we can continuously divide the number by $4$ again and again, until there are at most $2$ participants left. Now we can get the winner in one final query.
    284 
    285 **Solution**
    286 
    287 ```
    288 #include <bits/stdc++.h>
    289 
    290 using namespace std;
    291 
    292 int ask(vector<int> &k)
    293 {
    294 	cout << "? " << k[0] << ' ' << k[2] << endl;
    295 	int x;
    296 	cin >> x;
    297 	if (x == 1)
    298 	{
    299 		cout << "? " << k[0] << ' ' << k[3] << endl;
    300 		cin >> x;
    301 		if (x == 1) return k[0];
    302 		return k[3];
    303 	}
    304 	else if (x == 2)
    305 	{
    306 		cout << "? " << k[1] << ' ' << k[2] << endl;
    307 		cin >> x;
    308 		if (x == 1) return k[1];
    309 		return k[2];
    310 	}
    311 	else
    312 	{
    313 		cout << "? " << k[1] << ' ' << k[3] << endl;
    314 		cin >> x;
    315 		if (x == 1) return k[1];
    316 		return k[3];
    317 	}
    318 }
    319 
    320 void solve()
    321 {
    322 	int n;
    323 	cin >> n;
    324 	vector<int> a, b;
    325 	for (int i = 1; i <= (1LL << n); i++)
    326 	{
    327 		a.push_back(i);
    328 	}
    329 	while (a.size() > 2)
    330 	{
    331 		while (!a.empty())
    332 		{
    333 			vector<int> k(4);
    334 			k[0] = a.back();
    335 			a.pop_back();
    336 			k[1] = a.back();
    337 			a.pop_back();
    338 			k[2] = a.back();
    339 			a.pop_back();
    340 			k[3] = a.back();
    341 			a.pop_back();
    342 			int win = ask(k);
    343 			b.push_back(win);
    344 		}
    345 		a = b;
    346 		b.clear();
    347 	}
    348 	if (a.size() == 2)
    349 	{
    350 		cout << "? " << a[0] << ' ' << a[1] << endl;
    351 		int x;
    352 		cin >> x;
    353 		if (x == 2) a[0] = a[1];
    354 	}
    355 	cout << "! " << a[0] << endl;
    356 }
    357 
    358 int main(int argc, char ** argv)
    359 {
    360 	int tests;
    361 	cin >> tests;
    362 	while(tests--) solve();
    363 }
    364 ```
    365 
    366 **Feedback**
    367 
    368 * Didn't solve
    369 * Good problem
    370 * Average problem
    371 * Bad problem
    372 
    373 [1713E - Cross Swapping](https://codeforces.com/contest/1713/problem/E)
    374 
    375 **Hint 1**
    376 
    377 Think of the most to the least significant cell of the matrix.
    378 
    379 **Hint 2**
    380 
    381 How many positions in the matrix can a cell travel to after performing the operations?
    382 
    383 **Hint 3**
    384 
    385 And for each position that that cell can travel to, how many ways are there we can make it?
    386 
    387 **Tutorial**
    388 
    389 ### [1713E - Cross Swapping](https://codeforces.com/contest/1713/problem/E)
    390 
    391 Let's take a look at what the lexicographically smallest matrix is. Let's call $(x, y)$ a cell that is in the intersection of row $x$ and column $y$ of the matrix, and the integer written on that cell is $A_{x, y}$. A cell $(x_p, y_p)$ of this matrix is called more significant than the another cell $(x_q, y_q)$ if and only if $x_p \lt x_q$, or $x_p = x_q$ and $y_p \lt y_q$. The problem asks us to find the smallest matrix so the best suitable way to solve this problem is to traverse through the most to the least significant cell of the matrix, then determine if the current cell can be minimized or not.
    392 
    393 Suppose the current cell we are looking at is $(x, y)$. If $x = y$ then its position will not change after performing the operations. But if $x \neq y$, there are exactly $2$ operations that swap $(x, y)$ with another cell, that is $k = x$ and $k = y$. Both of these operations swap $(x, y)$ with the same cell $(y, x)$. So the only way we can minimize the value of $(x, y)$ is to try swapping it with $(y, x)$ (if $x \lt y$ and $A_{x, y} \gt A_{y, x}$) in some way.
    394 
    395 As a result we have our constructive algorithm. Remind that for each operation $k = i$ of the matrix ($1 \le i \le n$), there are $2$ states: it is being performed and not being performed. Suppose we have traversed to the cell $(x, y)$. If $x \ge y$, ignore it. If $x \lt y$ then we try to make $A_{x, y} = min(A_{x, y}, A_{y, x})$ by deciding to swap or not to swap the cells. If $A_{x, y} \gt A_{y, x}$, try to swap $(x, y)$ with $(y, x)$ by making $2$ operations $k = x$ and $k = y$ having different states. And if $A_{x, y} \lt A_{y, x}$ then we should keep their positions unchanged by making $2$ operations $k = x$ and $k = y$ having the same state. Note that if $A_{x, y} = A_{y, x}$, we do nothing.
    396 
    397 Let's implement this algorithm using a simple DSU where the $ith$ node represents the operation $k = i$. We define the value $par[u]$ in such a way that, suppose $p$ is the root of the $u$ node's component, $par[u] = p$ if $2$ operations $k = u$ and $k = p$ should have the same state, or $par[u] = -p$ if $2$ operations $k = u$ and $k = p$ should have different states. Define another function $join(i, j)$ to union $2$ nodes $i$ and $j$ to the same component. Note that $u$ and $-u$ are always in the same component and $par[-u] = -par[u]$. Thus, for the current cell $(x, y)$, we want to swap it with $(y, x)$ by calling $join(x, -y)$, or keep its position unchanged by calling $join(x, y)$.
    398 
    399 After constructing the graphs, the last thing to do is to determine which operations should be performed. One way to do so is for each root of the components of the DSU, we perform the operation which this root represents for. Then for other nodes just check $par[i] \gt 0$ for the $ith$ node and if it is true, the $k = i$ operation should be performed. When we have the list of the operations that need to be performed, we can bruteforcely perform each operation from the list one by one and the final matrix will be the lexicographically smallest matrix.
    400 
    401 Time complexity: $O(n^2)$
    402 
    403 **Solution**
    404 
    405 ```
    406 #include <bits/stdc++.h>
    407 using namespace std;
    408 
    409 const int N = 2e3 + 5;
    410 
    411 int n, a[N][N];
    412 
    413 int par[N];
    414 int getPar(int u) {
    415     if (u < 0) return -getPar(-u);
    416     if (u == par[u]) return u;
    417     return par[u] = getPar(par[u]);
    418 }
    419 void join(int u, int v) {
    420     u = getPar(u); v = getPar(v);
    421     if (abs(u) != abs(v)) {
    422         if (u > 0) par[u] = v;
    423         else par[-u] = -v;
    424     }
    425 }
    426 
    427 int main() {
    428     cin.tie(nullptr) -> sync_with_stdio(false);
    429 
    430     int tc; cin >> tc;
    431     while (tc--) {
    432         cin >> n;
    433         for (int i = 1; i <= n; i++)
    434             for (int j = 1; j <= n; j++) {
    435                 cin >> a[i][j];
    436             }
    437     
    438         iota(par + 1, par + n + 1, 1);
    439         // set par[i] == i for i in [1, n]
    440 
    441         for (int i = 1; i <= n; i++)
    442             for (int j = 1; j <= n; j++) {
    443                 if (a[i][j] < a[j][i]) join(i, j);
    444                 if (a[i][j] > a[j][i]) join(i, -j);
    445             }
    446     
    447         for (int i = 1; i <= n; i++) {
    448             if (getPar(i) < 0) continue;
    449             // we only perform the operation
    450             // if and only if getPar(i) > 0
    451             for (int j = 1; j <= n; j++)
    452                 swap(a[i][j], a[j][i]);
    453         }
    454 
    455         for (int i = 1; i <= n; i++) {
    456             for (int j = 1; j <= n; j++) {
    457                 cout << a[i][j] << ' ';
    458             }
    459             cout << '\n';
    460         }
    461     }
    462 }
    463 ```
    464 
    465 **Feedback**
    466 
    467 * Didn't solve
    468 * Good problem
    469 * Average problem
    470 * Bad problem
    471 
    472 [1713F - Lost Array](https://codeforces.com/contest/1713/problem/F)
    473 
    474 **Hint 0**
    475 
    476 * Is there any case that the answer doesn't exist?
    477 * If exist, are there multiple?
    478 
    479 **Hint 1**
    480 
    481 * How many times does $a_i$ contribute to $b_{j, n}$?
    482 
    483 **Hint 1.1**
    484 
    485 [Pascal's Triangle](https://en.wikipedia.org/wiki/Pascal%27s_triangle)
    486 
    487 $\rightarrow$ Calculate value that $a_i$ contribute to $b_{j, n}$.
    488 
    489 **Hint 1.2**
    490 
    491 [SierpiƄski triangle](https://en.wikipedia.org/wiki/Sierpi%C5%84ski_triangle)
    492 
    493 **Hint 2**
    494 
    495 Consider the inverse problem: Given array $a$. Construct $b_{j, n}$ for all $j$. How can you solve this problem?
    496 
    497 **Hint 3**
    498 
    499 Consider easier problem: Let construct matrix $g$ of size $(2n + 1) \times (n + 1)$ same way as matrix $b$. Given $g_{i, n}$ $(1 \le i \le 2n)$, please reconstruct $a$. How can you solve this problem?
    500 
    501 **Tutorial**
    502 
    503 ### [1713F - Lost Array](https://codeforces.com/contest/1713/problem/F)
    504 
    505 First, we can see that $a_i$ contribute $\binom{(n - i) + (j - 1)}{j - 1}$ times to $b_{j, n}$, which can calculate similar to [Pascal's Triangle](https://en.wikipedia.org/wiki/Pascal%27s_triangle). It's easy to see that the value that $a_i$ contribute to $b_{j, n}$ equal to $a_i$ when $\binom{(n - i) + (j - 1)}{j - 1}$ is odd, $0$ otherwise.
    506 
    507 Let's solve the inverse problem: Given array $a$. Construct $b_{j, n}$ for all $j$. $(1 \le j \le n)$
    508 
    509 By [Lucas Theorem](https://en.wikipedia.org/wiki/Lucas%27s_theorem), $\binom{(n - i) + (j - 1)}{j - 1}$ is odd when $(n - i)\ AND\ (j - 1) = 0$
    510 
    511 $\rightarrow (n - i)$ is a submask of $\sim(j - 1)$ (with $\sim a$ is inverse mask of $a$).
    512 
    513 Let define $m = 2^k$ with smallest $m$ satisfy $m \ge n$. Set $a'_i = a_i$ and $b'_j = b_{\sim(j - 1)} = b_{(m - 1) - (j - 1)}$ then $b'$ is the [Zeta transform](https://codeforces.com/blog/entry/45223) of $a'$.
    514 
    515 So we could apply [Mobius transform](https://codeforces.com/blog/entry/72488) in $b'$ to get $a'$. Since the operation is xor, mobius transform is as same as zeta transform. But unlike the inverse problem, there are some differences. We don't know the value of $b'_i$ for $i$ in $[0, m - n)$.
    516 
    517 Let $c$ be the sum over supermasks array of $b'$ (with $i$ is supermasks of $j$ when $i\ AND\ j = j)$, then set $c_k = 0$ for $k$ in $[m - n, m)$. After that, do another sum over supermasks on $c$ to get original value of $b'$. Now we can find $a'$ from $b'$ and $a$ from $a'$.
    518 
    519 Complexity: $O(nlog_2(n))$
    520 
    521 **Solution**
    522 
    523 ```
    524 #include <bits/stdc++.h>
    525 #include <ext/pb_ds/assoc_container.hpp>
    526 #include <ext/pb_ds/tree_policy.hpp>
    527 using namespace std;
    528 using namespace __gnu_pbds;
    529 
    530 #define endl '\n'
    531 #define fi first
    532 #define se second
    533 #define For(i, l, r) for (auto i = (l); i < (r); i++)
    534 #define ForE(i, l, r) for (auto i = (l); i <= (r); i++)
    535 #define FordE(i, l, r) for (auto i = (l); i >= (r); i--)
    536 #define Fora(v, a) for (auto v: (a))
    537 #define bend(a) (a).begin(), (a).end()
    538 #define isz(a) ((signed)(a).size())
    539 
    540 using ll = long long;
    541 using ld = long double;
    542 using pii = pair <int, int>;
    543 using vi = vector <int>;
    544 using vpii = vector <pii>;
    545 using vvi = vector <vi>;
    546 
    547 const int N = 1 << 19;
    548 
    549 int n;
    550 int a[N], b[N], ta[N], tb[N];
    551 int c[N];
    552 
    553 int m, lm, all1;
    554 
    555 signed main(){
    556     cin >> n;
    557     ForE(i, 1, n){
    558         cin >> b[i];
    559     }
    560 
    561     m = 1 << __lg(n);
    562     if (m < n){
    563         m *= 2;
    564     }
    565     lm = __lg(m);
    566     all1 = m - 1;
    567     memset(ta, -1, sizeof(ta));
    568     memset(tb, -1, sizeof(tb));
    569     ForE(i, 1, n){
    570         tb[all1 ^ (i - 1)] = b[i];
    571         ta[n - i] = -2;
    572     }
    573 
    574     For(i, 0, m){
    575         c[all1 ^ i] = max(tb[i], 0);
    576     }
    577     For(bit, 0, lm){
    578         For(msk, 0, m){
    579             if (msk >> bit & 1){
    580                 c[msk] ^= c[msk ^ (1 << bit)];
    581             }
    582         }
    583     }
    584     For(i, 0, m){
    585         if (tb[i] == -1){
    586             c[all1 ^ i] = 0;
    587         }
    588     }
    589     For(bit, 0, lm){
    590         For(msk, 0, m){
    591             if (msk >> bit & 1){
    592                 c[msk] ^= c[msk ^ (1 << bit)];
    593             }
    594         }
    595     }
    596     For(i, 0, m){
    597         if (tb[i] == -1){
    598             tb[i] = c[all1 ^ i];
    599         }
    600     }
    601 
    602     For(i, 0, m){
    603         ta[i] = tb[i];
    604     }
    605     For(bit, 0, lm){
    606         For(msk, 0, m){
    607             if (msk >> bit & 1){
    608                 ta[msk] ^= ta[msk ^ (1 << bit)];
    609             }
    610         }
    611     }
    612     ForE(i, 1, n){
    613         a[i] = ta[n - i];
    614     }
    615     ForE(i, 1, n){
    616         cout << a[i] << ' ';
    617     } cout << endl;
    618 }
    619 ```
    620 
    621 **Feedback**
    622 
    623 * Didn't solve
    624 * Good problem
    625 * Average problem
    626 * Bad problem