Giá trị xor lớn nhất

Submit solution
Points: 4
Time limit: 1.0s
Java 10 1.5s
Memory limit: 244M
Author:
cotyey
Problem type
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG

Cho một mảng số nguyên A gồm n phần tử và một danh sách Q gồm m truy vấn là các số nguyên. Nhiệm vụ của bạn là tìm giá trị lớn nhất của Qj ^ Ai trong đó 0≤j<m,0≤i<n và ký hiệu ^ là phép toán XOR của hai số nguyên.

Input:

  • Dòng đầu tiên là số nguyên N là độ dài của mảng.
  • Dòng thứ hai gồm N số nguyên Ai.
  • Dòng thứ ba gồm một số nguyên M là số lượng truy vấn.
  • M dòng tiếp theo mỗi dòng gồm một số nguyên Qj.
  • Trong đó: (1≤N,M≤105), (1≤Ai,Qj≤109)

Output:

Gồm M dòng với mỗi dòng là kết quả của từng truy vấn.

Example:

Input:

Copy
 3
 0 1 2
 3
 3
 7
 2

Output:

Copy
 3
 7
 3

Explanation:

A = [0, 1, 2]

Q0 = 3

  • 3 ^ 0 = 3 -> max = 3
  • 3 ^ 1 = 2 -> max = 3
  • 3 ^ 2 = 1 -> max = 3

Q1 = 7

  • 7 ^ 0 = 7 -> max = 7
  • 7 ^ 1 = 6 -> max = 7
  • 7 ^ 2 = 5 -> max = 7

Q2 = 2

  • 2 ^ 0 = 2 -> max = 2
  • 2 ^ 1 = 3 -> max = 3
  • 2 ^ 2 = 0 -> max = 3

Example 2:

Input:

Copy
 5
 5 1 7 4 3
 2
 2
 0

Output:

Copy
 7
 7

Comments


  • 0
    TICHPX  commented on Dec. 11, 2018, 3:33 p.m.

    Chặt nhị phân chăng?