D - Sum of Min of Xor
解説
/
実行時間制限: 5 sec / メモリ制限: 1024 MB
配点 : 700 点
問題文
長さ N の整数列 (A_1,A_2,\cdots,A_N) および (B_1,B_2,\cdots,B_N) が与えられます.
\sum_{1 \leq i < j \leq N} \min(A_i \oplus A_j, B_i \oplus B_j) の値を求めてください. ただしここで,\oplus はビットごとの排他的論理和を表します.
制約
- 1 \leq N \leq 250000
- 0 \leq A_i,B_i < 2^{18}
- 入力される値はすべて整数である
入力
入力は以下の形式で標準入力から与えられる.
N A_1 A_2 \cdots A_N B_1 B_2 \cdots B_N
出力
答えを出力せよ.
入力例 1
3 1 2 3 4 5 6
出力例 1
4
- \min(1 \oplus 2, 4 \oplus 5)=\min(3,1)=1
- \min(1 \oplus 3, 4 \oplus 6)=\min(2,2)=2
- \min(2 \oplus 3, 5 \oplus 6)=\min(1,3)=1
よって,答えは 1+2+1=4 になります.
入力例 2
4 1 2 3 4 1 2 3 4
出力例 2
24
入力例 3
10 195247 210567 149398 9678 23694 46151 187762 17915 176476 249828 68649 128425 249346 62366 194119 117620 26327 161384 207 57656
出力例 3
4019496
Score : 700 points
Problem Statement
Given are sequences of N integers each: (A_1,A_2,\cdots,A_N) and (B_1,B_2,\cdots,B_N).
Find \sum_{1 \leq i < j \leq N} \min(A_i \oplus A_j, B_i \oplus B_j), where \oplus denotes the bitwise XOR.
Constraints
- 1 \leq N \leq 250000
- 0 \leq A_i,B_i < 2^{18}
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N A_1 A_2 \cdots A_N B_1 B_2 \cdots B_N
Output
Print the answer.
Sample Input 1
3 1 2 3 4 5 6
Sample Output 1
4
- \min(1 \oplus 2, 4 \oplus 5)=\min(3,1)=1
- \min(1 \oplus 3, 4 \oplus 6)=\min(2,2)=2
- \min(2 \oplus 3, 5 \oplus 6)=\min(1,3)=1
Thus, the answer is 1+2+1=4.
Sample Input 2
4 1 2 3 4 1 2 3 4
Sample Output 2
24
Sample Input 3
10 195247 210567 149398 9678 23694 46151 187762 17915 176476 249828 68649 128425 249346 62366 194119 117620 26327 161384 207 57656
Sample Output 3
4019496