F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist

C/C++/Java Exams
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
DIY | Web-DIY beta
Register new ID

# Memory

Time Limit: 8000/4000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 562    Accepted Submission(s): 171
Special Judge

Problem Description
Little Bob¡¯s computer has 2n bytes of memory. For convenience, n-bit integers 0 to 2n - 1 are used to index these bytes.

Now he wants to assign a value to each byte of the memory. In this problem, a byte is composed of m bits. Therefore he can only assign 0 to 2m - 1 (inclusive) to a single byte.

Bob has some preferences on which value to be assigned to each byte. For the byte indexed by i, if it is assigned with value j (0 ¡Ü j < 2m), the preference score for it is wi,j.

In addition, each byte has a threshold value. For two different bytes indexed by a and b, if the following two conditions are satisfied, there will be an additional score (ua xor ub):

1.a and b only have one bit of difference in their binary forms;

2.The assigned value of byte a is not less than its threshold value, or the assigned value of byte b is not less than its threshold value.

The total score of an assignment solution is the sum of the preference scores of all bytes plus the sum of all additional scores.

Bob wants to find an assignment solution with the maximum total score. If there are multiple solutions, you can output any of them.

Input
The first line contains an integer T (T ¡Ü 3), denoting the number of the test cases.

For each test case, the first line contains two integers, n and m(1 ¡Ü n, m ¡Ü 8), as mentioned above. The second line contains 2n integers, and the i-th integer is the threshold value for byte i. The threshold values are between 0 and 2m - 1, inclusively. The third line contains 2n integers, and the i-th integer is ui(0 ¡Ü ui < 1024). The next 2n lines give all preference scores. Each line contains 2m integers, and the j-th integer of the i-th line is wi,j (-1024 ¡Ü wi,j < 1024).

Output
For each test case, output one line consisting of 2n integers between 0 and 2m - 1, and the i-th integer is the value assigned to byte i in the assignment solution with the maximum total score.

Sample Input
1
3 2
0 1 1 3 3 0 3 3
4 8 8 7 0 9 2 9
-9 -8 3 2
-9 -6 4 1
-6 -8 -5 3
3 -1 -4 -1
-6 -5 1 10
-10 7 3 -10
-3 -10 -4 -5
-2 -1 -9 1

Sample Output
2 2 3 0 3 1 0 3

Source

Statistic | Submit | Discuss | Note
 Home | Top Hangzhou Dianzi University Online Judge 3.0 Copyright © 2005-2024 HDU ACM Team. All Rights Reserved. Designer & Developer : Wang Rongtao LinLe GaoJie GanLu Total 0.000000(s) query 1, Server time : 2024-06-17 01:42:41, Gzip enabled Administration