Larry and Nerdiness

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 4.0s
Memory limit: 256M

Problem types

Larry is a large nerd, and thus likes nerdy things. Larry has two arrays of length N: a and k. Larry considers some sequence of integers i_1 \ldots i_m nerdy if:

1 \leq i_1 < i_2 < \ldots < i_m \leq N. The sequence is increasing.

Popcount\left(a_{i_{j-1}} \& a_{i_j}\right) = k_{i_j} for all 1 < j \leq M, where & is bitwise and, and Popcount is the number of one bits in the binary representation of its argument.

Find the longest nerdy sequence.

Input Specification

The first line will contain one integer N\ (1 \leq N \leq 10^5).

The second line will contain N integers a_i\ (0 \leq a_i < 2^{20}).

The last line will contain N integers k_i\ (0 \leq k_i \leq 20).

Output Specification

On the first line you are to output one integer, the length of the longest nerdy sequence.

On the next line you are to print any such longest sequence, separated by spaces.


Subtask 1 (7%)

1 \leq N \leq 15

Subtask 2 (16%)

1 \leq N \leq 5000

Subtask 3 (17%)

0 \leq a_i < 2^8

Subtask 4 (60%)

No further constraints.

Sample Input

5 3 5 3 5
10 1 20 1 20

Sample Output

1 2


There are no comments at the moment.