fork download
copy 
  1. import java.util.Scanner;
  2. import java.util.Stack;
  3.  
  4. public class Main {
  5.  
  6.     public static void main (String[] args) {
  7.         Scanner scanner = new Scanner(System.in);
  8.         int t = scanner.nextInt();
  9.         while(t>0) {
  10.             int n = scanner.nextInt();
  11.             int temp_int;
  12.             int[] arr = new int[n+1];
  13.             arr[0] = 0;
  14.             Vertex vertex = new Vertex();
  15.             Stack stack = new Stack();
  16.             for(int i = 1; i <= n; i++) {
  17.                 stack.clear();
  18.                 arr[i] = scanner.nextInt();
  19.                 arr[i] = arr[i-1] ^ arr[i];
  20.  
  21.                 temp_int = arr[i];
  22.                 while(temp_int > 0) {
  23.                     stack.push(temp_int%2);
  24.                     temp_int /= 2;
  25.                 }
  26.                 while(stack.size() < 32)
  27.                     stack.push(0);
  28.  
  29.                 addNum(vertex, stack, i);
  30.             }
  31.             long res = 0;
  32.             int idx;
  33.             for(int i = 1; i <= n; i++) {
  34.                 temp_int = arr[i];
  35.                 while(temp_int > 0) {
  36.                     stack.push(temp_int%2);
  37.                     temp_int /= 2;
  38.                 }
  39.                 while(stack.size() < 32)
  40.                     stack.push(0);
  41.  
  42.                 idx = maxXor(vertex, stack);
  43.                 if ((arr[i] ^ arr[idx]) > res)
  44.                     res = (arr[i] ^ arr[idx]);
  45.             }
  46.             System.out.println(res);
  47.             t--;
  48.         }
  49.     }
  50.  
  51.     public static void addNum(Vertex vertex, Stack stack, int idx) {
  52.         if(stack.isEmpty()) {
  53.             vertex.idx = idx;
  54.         } else {
  55.             int next_bit = (int) stack.pop();
  56.             if (vertex.vertexes[next_bit] == null)
  57.                 vertex.vertexes[next_bit] = new Vertex();
  58.             addNum(vertex.vertexes[next_bit], stack, idx);
  59.         }
  60.     }
  61.  
  62.     public static int maxXor(Vertex vertex, Stack stack) {
  63.         if(stack.isEmpty())
  64.             return vertex.idx;
  65.  
  66.         int num = (int) stack.pop();
  67.         if(num == 0) {
  68.             if(vertex.vertexes[1] != null)
  69.                 return maxXor(vertex.vertexes[1], stack);
  70.             else if(vertex.vertexes[0] != null)
  71.                 return maxXor(vertex.vertexes[0], stack);
  72.             else
  73.                 return 0;
  74.         } else {
  75.             if(vertex.vertexes[0] != null)
  76.                 return maxXor(vertex.vertexes[0], stack);
  77.             else
  78.                 return 0;
  79.         }
  80.     }
  81. }
  82.  
  83. class Vertex {
  84.     int idx;
  85.     Vertex[] vertexes = new Vertex[2];
  86.     Vertex() {
  87.         idx = -1;
  88.         vertexes[0] = null;
  89.         vertexes[1] = null;
  90.     }
  91. }
Runtime error #stdin #stdout #stderr 0.14s 321088KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
Exception in thread "main" java.util.NoSuchElementException
	at java.util.Scanner.throwFor(Scanner.java:862)
	at java.util.Scanner.next(Scanner.java:1485)
	at java.util.Scanner.nextInt(Scanner.java:2117)
	at java.util.Scanner.nextInt(Scanner.java:2076)
	at Main.main(Main.java:8)
https://ideone.com/WuXLNz
language:
Java (HotSpot 12)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!