AND Sorting (Codeforces 1682B)
Tags: Others, bitmasks

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>p_{i+1}$$$ for at least one $$$1 \le i \le n - 1$$$). 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:   Choose two indices $$$i$$$ and $$$j$$$ $$$(1 \le i \lt j \le n)$$$ such that $$$p_i \& p_j = X$$$.  Swap $$$p_i$$$ and $$$p_j$$$. Here $$$\&$$$ denotes the bitwise AND operation.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.

Input: 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.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.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.It is guaranteed that the sum of $$$n$$$ over all cases does not exceed $$$2 \cdot 10^5$$$.

Output: For each test case output a single integer — the maximum value of $$$X$$$ such that $$$p$$$ is $$$X$$$-sortable.

Note: 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$$$.Sorting using $$$X = 0$$$:   Swap $$$p_1$$$ and $$$p_4$$$, $$$p = [2, 1, 3, 0]$$$.  Swap $$$p_3$$$ and $$$p_4$$$, $$$p = [2, 1, 0, 3]$$$.  Swap $$$p_1$$$ and $$$p_3$$$, $$$p = [0, 1, 2, 3]$$$. Sorting using $$$X = 2$$$:   Swap $$$p_3$$$ and $$$p_4$$$, $$$p = [0, 1, 2, 3]$$$. In the second test case, we must swap $$$p_1$$$ and $$$p_2$$$ which is possible only with $$$X = 0$$$.

Sample Inputs:
4
4
0 1 3 2
2
1 0
7
0 1 2 3 5 6 4
5
0 3 2 1 4

Sample Outputs:
2
0
4
1

Solution (Python):
import sys
import copy
import heapq
import bisect
import functools
from math import *
from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import groupby
import itertools
from itertools import accumulate
from decimal import Decimal, ROUND_HALF_UP
readline = lambda : sys.stdin.readline().rstrip()

def solve():
    n = int(readline())
    a = list(map(int, readline().split()))
    ans = (1 << 31) - 1
    for (i, x) in enumerate(a):
        if x != i:
            ans &= x
    print(ans)

def main():
    t = 1
    t = int(readline())
    for i in range(t):
        solve()
if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = lambda : sys.stdin.readline().strip()
intput = lambda : map(int, input().split())

def solve():
    (N,) = intput()
    P = [*intput()]
    AND = (1 << 32) - 1
    for (i, x) in enumerate(P):
        if x != i:
            AND &= x
    return AND
if __name__ == '__main__':
    (T,) = intput()
    for _ in range(T):
        print(solve())

Solution (Python):
for s in [*open(0)][2::2]:
    r = ~0
    i = 0
    for x in map(int, s.split()):
        r &= (x, ~0)[x == i]
        i += 1
    print(r)