problem in solving nikitosh and xor problem

I solved THIS PROBLEM. I solved it using trie, my code is not working for all test cases in sub task 2, I am getting TLE. Can any one help me to figure out what is the mistake in my code. If you didn’t understand anything in code the do write in comments.

Your code works fine, the problem is in the test cases, the test cases in which your code goes time out are very tight.
Hence you need some optimization.

Some optimization for you :

1 : Use fast input/output like take input/output in char or search on the internet for fast i/o in java , like in c/c++ :
get-char/put-char techniques are available.

2 : Construct your Trie data structure with the help of array’s, it works fast on array’s due to good
accessing time ( Link : )

3 : During input convert each number into binary and store using char array make 2-D array of size 31 * N, then you can simply tell’s whether ith bit of any particular number is ON or OFF

4 : Don’t run linear loop for N, many times, answer can be calulated in two runs, during input you can calculate prefix max xor from left, then during second run you can calculate prefix max xor from right and update your answer , without storing results from right.

I think these optimization are enough to pass all the test cases.

Thanks for advice given


I am not able to create array of size a[10000000][2] in java. What should I do.

Declare it globally, it work’s on codechef ide.