Xor Sort


Submit solution

Points: 100 (partial)
Time limit: 2.0s
Python 3 25.0s
Memory limit: 256M
Python 3 1G

Authors:
Problem types

It's been one year since the first arena contest! In a year we hosted many rated contests and we look forward to hosting more frequent contests in the future.

After each rated contest, participants' ratings change. Your tasks is to write a new rating algorithm.

You will be given an array \(a\) of \(n\) integers, where \(a_i\) represents the rating of the \(ith\) contestant, from the bottom of the standing (contestant \(1\) was the last one). Your objective is to make this array sorted in non-decreasing order by doing the following operation :

For each \(i\) starting from the beginning of the array (\(i = 1\)) to the end (\(i = n\)) you can choose one index \(j > i\) and replace \(a_i\) with \(a_i\) \(xor\) \(a_j\), or you can skip this index \(i\) and not perform any operation at all.

Elements should be modified in the same order they appear in the array, that is, element \(a_p\) cannot be modified if any element \(a_q, q > p\) was already modified.

Input Specification

The first line of the input contains one integer \(t\) (\( 1\leq t \leq 10^4\)) - the number of test cases. Then \(t\) test cases follow.

Each test case contains two lines. The first line of each test case contains one integer \(n\) (\( 1 \leq n \leq 10^5\)) - the number of elements in the array.

The second line of the test case contains \(n\) integers \(a_1,a_2,...,a_n\) (\( 0 \leq a_i \leq 10^9\)).

It is guaranteed that the sum of n over all test cases does not exceed \(10^5\).

Output Specification

For each test case, in a new line output "YES" if it is possible to sort the array in non descending order otherwise print "NO"

Scoring

  • (6 points) \(1 \leq n \leq 10^5\) and \( a_i \leq 32 \)

  • (6 points) \( 1 \leq n \leq 10^5 \) and \(a_i\) is a power of \(2\)

  • (10 points) sum of \(n\) over all test cases does not exceed \(2000\)

  • (18 points) no additional constraints

Sample Input

3
5
17 16 0 16 16
5
2 27 30 16 16
4
7 7 7 1

Sample Output

YES
YES
NO

Comments

There are no comments at the moment.