codeforces-scrape

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

1682B.md (2200B)


      1 Source: https://codeforces.com/problemset/problem/1682/B
      2 
      3 B. AND Sorting
      4 
      5 time limit per test
      6 
      7 1 second
      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 You are given a permutation $p$ of integers from $0$ to $n-1$ (each of them occurs exactly once). Initially, the permutation is not sorted (that is, $p_i \gt p_{i+1}$ for at least one $1 \le i \le n - 1$).
     22 
     23 The permutation is called $X$-sortable for some non-negative integer $X$ if it is possible to sort the permutation by performing the operation below some finite number of times:
     24 
     25 * Choose two indices $i$ and $j$ $(1 \le i \lt j \le n)$ such that $p_i \& p_j = X$.
     26 * Swap $p_i$ and $p_j$.
     27 
     28 Here $\&$ denotes the [bitwise AND operation](https://en.wikipedia.org/wiki/Bitwise_operation#AND).
     29 
     30 Find the maximum value of $X$ such that $p$ is $X$-sortable. It can be shown that there always exists some value of $X$ such that $p$ is $X$-sortable.
     31 
     32 Input
     33 
     34 The input consists of multiple test cases. The first line contains a single integer $t$ $(1 \le t \le 10^4)$  — the number of test cases. Description of test cases follows.
     35 
     36 The first line of each test case contains a single integer $n$ $(2 \le n \le 2 \cdot 10^5)$  — the length of the permutation.
     37 
     38 The second line of each test case contains $n$ integers $p_1, p_2, ..., p_n$ ($0 \le p_i \le n-1$, all $p_i$ are distinct)  — the elements of $p$. It is guaranteed that $p$ is not sorted.
     39 
     40 It is guaranteed that the sum of $n$ over all cases does not exceed $2 \cdot 10^5$.
     41 
     42 Output
     43 
     44 For each test case output a single integer — the maximum value of $X$ such that $p$ is $X$-sortable.
     45 
     46 Example
     47 
     48 Input
     49 
     50 ```
     51 4
     52 
     53 4
     54 
     55 0 1 3 2
     56 
     57 2
     58 
     59 1 0
     60 
     61 7
     62 
     63 0 1 2 3 5 6 4
     64 
     65 5
     66 
     67 0 3 2 1 4
     68 ```
     69 
     70 Output
     71 
     72 ```
     73 2
     74 0
     75 4
     76 1
     77 ```
     78 
     79 Note
     80 
     81 In the first test case, the only $X$ for which the permutation is $X$-sortable are $X = 0$ and $X = 2$, maximum of which is $2$.
     82 
     83 Sorting using $X = 0$:
     84 
     85 * Swap $p_1$ and $p_4$, $p = [2, 1, 3, 0]$.
     86 * Swap $p_3$ and $p_4$, $p = [2, 1, 0, 3]$.
     87 * Swap $p_1$ and $p_3$, $p = [0, 1, 2, 3]$.
     88 
     89 Sorting using $X = 2$:
     90 
     91 * Swap $p_3$ and $p_4$, $p = [0, 1, 2, 3]$.
     92 
     93 In the second test case, we must swap $p_1$ and $p_2$ which is possible only with $X = 0$.