3058:Rikka with Stable Marriage

People in love always feel humble. Sometimes, Rikka is worried about whether she deserves love from Yuta.

Stable marriage problem is an interesting theoretical model which has a strong connection with the real world. Given

n men and

n women, where each person has ranked all members of the opposite sex in order of preference. We use a permutation

p of length

n to represent a match that the

ith man gets married with the

pith woman. A match is stable if and only if there are no two people of opposite sexes who would both rather have each other than their current partners, i.e.,

∀i≠j,¬(ri(pj,pi)∧rpj(i,j)) where

ra(b,c) represents whether person

a loves

b more than

c.

Rikka wants to resolve the confusion in her mind by considering a special case of the stable marriage problem. Rikka uses a feature integer to represents a person's character, and for two persons with feature integers equal to

x and

y, Rikka defines the suitable index of them as

x⊕y, where

⊕ represents binary exclusive-or.

Given

n men with feature integers

a1,…,an and

n women with feature integers

b1,…,bn. For the

ith man, he loves the

jth woman more than the

kth woman if and only if

ai⊕bj>ai⊕bk; for the

ith woman, she loves the

jth man more than the

kth man if and only if

bi⊕aj>bi⊕ak.

Rikka wants to calculate the best stable match for this problem, i.e., let

P be the set of all stable match, she wants to calculate

maxp∈P(∑ni=1(ai⊕bpi)). Since

n is quite large, this problem is too difficult for Rikka, could you please help her find the answer?

The first line of the input contains a single integer

T(1≤T≤50), the number of test cases.

For each test case, the fisrt line contains a sigle integer

n(1≤n≤105).

The second line contains

n integers

a1,…,an(1≤ai≤109) which represents the feature number of each man.

The third line contains

n integers

b1,…,bn(1≤bi≤109) which represents the feature number of each woman.

The input guarantees that there are no more than

5 test cases with

n>104, and for any

i,j∈[1,n],i≠j,

ai≠aj and

bi≠bj.

For each test case, output a single line with a single integer, the value of the best stable match. If there is no stable match, output

−1.

Time Limit	$5$ 秒/Second(s)	Memory Limit	$512$ 兆字节/Megabyte(s)
提交总数	$2$	正确数量	$2$
裁判形式	标准裁判/Standard Judge	我的状态	尚未尝试
难度		分类标签

本题记录	用户（点击查看用户）	运行号（点击购买题解）	时间
算法最快[$2765 $ms]	淡意的温柔	588059	2020-05-27 09:46:47
内存最少[$74744 $KB]	淡意的温柔	588059	2020-05-27 09:46:47
第一AC	淡意的温柔	588058	2020-05-27 09:45:46
第一挑战	淡意的温柔	588058	2020-05-27 09:45:46

3058: Rikka with Stable Marriage

Description

Input

Output

Sample Input复制

Sample Output复制

推荐代码查看3058 所有题解  上传题解视频得图灵币

赛题来源/所属竞赛 2019 Multi-University Training Contest 9 N/A