Delicious Pineapple Pizza
InterviewTime limit1sMemory limit256 MB
Pair each pineapple with a dough to make N pizzas, maximizing the smallest XOR value over all pairs.
- Level
Medium7 of 10
- Topics
- Binary search, Bit manipulation, Greedy, Math
- Solved
- No attempts yet
Problem
Byeongchan runs "Pineapple Pizza is A Pizza", or PPAP for short, a company that makes very delicious pineapple pizza. But a rival company, doubting PPAP's pineapple pizza, has filed a complaint against PPAP! To defend the company, Byeongchan must make pineapple pizzas of the highest possible quality.
How delicious a pineapple pizza is depends on how good the pineapple and the dough are. If the pineapple has quality and the dough has quality , the pizza has taste . Byeongchan has pineapples and doughs in total, and must use them to make pineapple pizzas. To prove that he always makes the finest pineapple pizza, Byeongchan wants to maximize the minimum taste among the special pineapple pizzas.
Input
The first line gives (1 ≤ ≤ 100).
The second line gives integers (1 ≤ ≤ ). The third line gives integers (1 ≤ ≤ ).
Output
Find the maximum possible value of the minimum taste among the pineapple pizzas.
Hint
If the pineapple-dough pairs are (1,2), (2,5), (3,4), (4,3), (5,1), then 1 XOR 2 = 3, 2 XOR 5 = 7, 3 XOR 4 = 7, 4 XOR 3 = 7, 5 XOR 1 = 4, so the minimum is 3. Other pairings also give a minimum of 3, but no pairing gives a minimum of 4 or more.