DMOPC '18 Contest 1 P5 - Sorting

View as PDF

Submit solution

Points: 12 (partial)
Time limit: 1.0s
Java 2.5s
Java 15 2.5s
Python 2.5s
Memory limit: 256M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

You are considering a permutation P of 0 to N-1 and a non-negative integer C. The elements at indices i and j may be swapped only if P_i \oplus P_j \le C where A\oplus B denotes the XOR of A and B. However, C has not yet been decided. What is the smallest possible non-negative integer C so that this permutation may be sorted from least to greatest?

To make this more interesting, the permutation will be updated. You are given Q updates of the form u v meaning that P_u and P_v have been swapped. After each of the Q updates, what is the best C?

Note that the indices are 1-indexed, but the values are from 0 to N-1.


For all 1\le i\le N,\ 0\le P_i\le N-1.
P is a permutation, so each element from 0 to N-1 will appear exactly once.
1\le u, v\le N

Subtask 1 [20%]

1\le N\le 400
1\le Q\le 400

Subtask 2 [30%]

1\le N\le 200\,000

Subtask 3 [30%]

1\le N\le 50\,000
1\le Q\le 50\,000

Subtask 4 [20%]

1\le N\le 200\,000
1\le Q\le 200\,000

Input Specification

The first line will contain two space-separated integers, N and Q.
The next line will contain N space-separated integers, P_1, P_2, \dots, P_N.
The following Q lines will each contain two space-separated integers, u and v, the indices to be swapped.

Output Specification

For each query, output a line containing a single non-negative integer, the smallest possible C given the current permutation.

Sample Input 1

4 2
2 3 1 0
4 3
1 1

Sample Output 1


Explanation for Sample 1

After the first update, the permutation is 2, 3, 0, 1. Swap 2 and 0, then 3 and 1.
The second update doesn't change anything.

Sample Input 2

4 3
1 0 2 3
1 2
3 4
1 4

Sample Output 2



There are no comments at the moment.