Description

 

This is a partial judge problem.

You need to maintain a multiset of non-negative integers. Each integer is represented as a fixed-length binary string of length 30. The same integer may be inserted multiple times, and each occurrence is counted separately.

You need to implement a binary trie to support the following functions:

void decimal_to_binary(unsigned int x, char ans[]);
void insert_number(Node *root, char s[]);
void delete_number(Node *root, char s[]);
int count_prefix(Node *root, char p[]);
int kth_largest_xor(Node *root, char x[], int k);

Binary Trie Node

The judge provides the following node structure:

typedef struct Node {
    int pass_count;
    int end_count;
    struct Node *child[2];
} Node;

• pass_count: how many current numbers pass through this node.
• end_count: how many current numbers end exactly at this node.
• child[0] and child[1]: the next bit in the binary trie.

The judge provides:

Node* create_node(void);

You may call create_node() inside insert_number when a new child node is needed.

Bitwise XOR

The operator xor means bitwise exclusive OR. For each bit:

0 xor 0 = 0
0 xor 1 = 1
1 xor 0 = 1
1 xor 1 = 0

When applying xor to two integers, compare their binary representations bit by bit.

5  = 000000000000000000000000000101
2  = 000000000000000000000000000010
5 xor 2 = 000000000000000000000000000111 = 7

Required Functions

Decimal To Binary

void decimal_to_binary(unsigned int x, char ans[]);

Convert decimal integer x into a 30-bit binary string and write it into ans. The string must be null-terminated.

Insert

void insert_number(Node *root, char s[]);

Insert one occurrence of the 30-bit binary string s into the multiset.

Delete

void delete_number(Node *root, char s[]);

Delete one occurrence of the 30-bit binary string s. It is guaranteed that the number currently exists.

Count Prefix

int count_prefix(Node *root, char p[]);

Return the number of integers whose 30-bit binary representation has prefix p.

Kth Largest XOR

int kth_largest_xor(Node *root, char x[], int k);

Return the kth largest value among all values a xor x, where a is an integer currently in the multiset. The string x is a 30-bit binary string. The return value must be the decimal value of the kth largest XOR result.

Scoring

The score is based on the ratio of accepted test cases. The intended subtasks are:

10%  Decimal to binary only.
     Only operation 5 appears.

20%  Prefix count without delete.
     Operations: 1, 3.

20%  Prefix count with delete.
     Operations: 1, 2, 3.

20%  Kth largest with xor value 0.
     Operations: 1, 2, 4.
     In every operation 4, the query string s is 000...000.

20%  Maximum XOR only.
     Operations: 1, 2, 4.
     In every operation 4, k is always 1.

10%  Full binary version.
     Operations: 1, 2, 3, 4.

Only the first 10% subtask contains operation 5. All other subtasks use only binary-string operations, so students who cannot implement decimal conversion can still solve up to 90% of the tests.

Input

The first line contains one integer Q, the number of operations.

Each of the next Q lines contains one operation in one of the following formats:

1 s
2 s
3 p
4 s k
5 x

The meaning of each operation is:

• 1 s: insert 30-bit binary string s.
• 2 s: delete 30-bit binary string s.
• 3 p: output the number of current integers whose binary representation has prefix p.
• 4 s k: output the kth largest value of a xor value(s), where s is a 30-bit binary string.
• 5 x: output the 30-bit binary representation of decimal integer x.

Constraints

1 <= Q <= 200000
BIT_LEN = 30
0 <= x < 2^30
|s| = 30 for operations 1, 2, and 4
1 <= |p| <= 30 for operation 3
1 <= k <= current multiset size for operation 4

• Binary strings contain only 0 and 1.
• For every delete operation, the number to be deleted currently exists.
• The multiset is non-empty whenever a kth largest XOR query is called.
• The same number may appear multiple times in the multiset.
• Since every inserted binary string has length 30, the number of trie nodes created is at most 1 + 30 * Q.

Output

For each operation 3, output one integer: the return value of count_prefix.

For each operation 4, output one integer: the return value of kth_largest_xor.

For each operation 5, output one 30-bit binary string: the result written by decimal_to_binary.

Each answer should be printed on its own line.

Sample Explanation

The first operation converts decimal 5 into its 30-bit binary representation.

Then the binary values for 5, 9, and 7 are inserted.

When the query value is 0, the XOR results are just the original numbers. Therefore, the 2nd largest value among {5, 7, 9} is 7.

For query value 2, the XOR results are:

5 xor 2 = 7
9 xor 2 = 11
7 xor 2 = 5

The largest result is 11.

Sample Input  Download

Sample Output  Download

Partial Judge Code

14944.c

Partial Judge Header

14944.h

Tags

Discuss