Description

Mr. Lu is a famous magician. There’s a poker magic tutorial on his youtube channel.
There’re N stacks of cards on the table at begining.
And then, Mr. Lu make M actions on these card stacks.
There’s only two kinds of actions Merge and Cut:

• Merge x y: put the x-th card stack on the top of y-th card stack.
• Cut x i: cut the x-th card stack into two stacks. One is the card stack contains ( 1~i )-th cards of original stack. The other one is the remaining. The former’s index will be x, the latter’s will be (x+1)
• The indexes of stacks and cards will be changed after Merge and Cut.

For example:

As a lazy CS student, you only focus on the result.
Therefore, you decide to write a program to compute the final state of card stacks.

It’s partial judge for this problem.
Please download the code at the bottom to see the interface and main function.
You have to implement a data structure like below:

Input

Two integer N,M on the first line.
For each of the next N lines, there’re several integers Ni and Ci,1,Ci,2...Ci,Ni.
Ni means the number of cards in the i-th stack.
Ci,j denotes the j-th card of i-th stack.

The folloing M lines contains one action per line.
Every Action is one of “Merge x y” or “Cut x i”.

It’s guaranteed that:

• 1 ≤ N, M ≤ 9000
• ∑ Ni ≤ 4∗10⁴
• Ci,j is non-negative integer.
• In “Merge x y” action:
  • the x, y-th stacks always exist.
  • x is not equal to y.
• In “Cut x i” action:
  • the x-th stack always exists.
  • i is always between 1 and Nx - 1.
• There’s at least 1 card in each card stack.

Output

Print the card stacks by the order of index.
One line for one card stack.

Please refer to the sample input/output for the precise format.
There is a ‘\n’ at the end of each line.

Sample Input  Download

Sample Output  Download

Partial Judge Code

12680.c

Partial Judge Header

12680.h

Tags

Discuss

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

Description

 

Given several Boolean expressions, you need to handle three types of queries:

1. Expand the custom operator @.
2. Convert an infix expression into the preorder traversal of its syntax tree.
3. Expand the custom operator @, build the syntax tree, and evaluate the expression.

The expressions may contain the following characters:

0 1 & | ^ @ ( )

There are no spaces inside an expression.

Grammar

After all custom operators are expanded, the expression will contain only:

0 1 & | ^ ( )

To parse the infix expression with parentheses, use the grammar below.

EXPR   = FACTOR | FACTOR OP EXPR
FACTOR = ID | (EXPR)
ID     = 0 | 1
OP     = one of &, |, ^

All ordinary operators &, |, and ^ are parsed by this grammar. That is, they have the same precedence and are right-associative.

For example, 0|1&0 is parsed as 0|(1&0), so the preorder traversal of its syntax tree is |0&10.

Do not use the usual C operator precedence. Always use the grammar given in this problem.

Custom Operator

The custom operator @ is an infix binary operator.

For each custom operator:

• a is the nearest valid FACTOR immediately on its left.
• b is the nearest valid FACTOR immediately on its right.

The custom operator is defined as:

a @ b = a|b&a

When expanding @, directly replace a@b with a|b&a. Do not add extra parentheses. Only the parentheses that already belong to a or b should remain.

You must repeatedly perform the following operation:

1. Find the leftmost @ in the current expression.
2. Find its left operand a, the nearest FACTOR immediately on its left.
3. Find its right operand b, the nearest FACTOR immediately on its right.
4. Replace a@b with a|b&a.
5. The new expression becomes the current expression.
6. Repeat until there is no @.

Expansion Examples

0@1
=> 0|1&0

(0^1)@0
=> (0^1)|0&(0^1)

0@(1|0)
=> 0|(1|0)&0

For multiple custom operators, always expand the leftmost one first.

Query Types

Each test case contains a query type and an expression.

Type 1: Expand Custom Operators

For query type 1, output the expression after expanding all @. The output should contain no @.

Type 2: Infix To Syntax Tree Preorder

For query type 2, the input expression contains no @. Build the syntax tree using the grammar in this problem, then output the preorder traversal of the syntax tree.

Type 3: Evaluate The Expression

For query type 3, first expand all @. Then build the syntax tree using the grammar in this problem and evaluate the expression.

a & b = bitwise AND
a | b = bitwise OR
a ^ b = bitwise XOR

Since all operands are Boolean values, the answer is always 0 or 1.

Partial Judge

This is a partial judge problem. The judge provides main.c and function.h. The style is similar to the original infix-to-syntax-tree problem.

The judge provides:

BTNode* makeNode(char c);
void printPrefix(BTNode *root);
void freeTree(BTNode *root);

You only need to implement the following functions:

void replace_custom_operator(char expr[], char result[]);
BTNode* EXPR(void);
BTNode* FACTOR(void);
int evaluateTree(BTNode *root);

The global variable expr[] stores the expression currently being parsed. The global variable pos stores the current parsing position. The parser is intended to parse from the beginning of the expression.

Constraints

1 <= N <= 1000
1 <= |expression| <= 2000
After expanding all @, the expression length will not exceed 50000.

• Expressions contain only 0, 1, &, |, ^, @, (, and ).
• Expressions are valid.
• Parentheses are matched.
• Type 2 expressions do not contain @.
• There are 10 test cases.

Scoring

The score is based on the ratio of accepted test cases.

20%  Type 1, custom operator without parentheses.
     The operands of every @ are both IDs.

20%  Type 1, custom operator with FACTOR operands.
     The operands of @ may be parenthesized expressions.

20%  Type 2, syntax tree without parentheses.
     Expressions contain no parentheses and no @.

20%  Type 2, syntax tree with parentheses.
     Expressions may contain parentheses, but no @.

20%  Type 3, evaluation.
     Expressions may contain @ and parentheses.

Sample Explanation

For the first query:

0@1
=> 0|1&0

For the third query, 0|1&0 is parsed as 0|(1&0), so the preorder traversal is |0&10.

For the fifth query:

0@1^1
=> 0|1&0^1

By the grammar, this is parsed as 0|(1&(0^1)), and the value is 1.

 

Extra Note

This note is only for extra background and is not needed for solving the problem. The expansion rule for @ is a simplified rule designed for this problem. It is closer to macro expansion or textual replacement, such as #define, than to how a parser usually handles operators.

Input

The first line contains one integer N, the number of queries.

Each of the next N lines contains one query in the following format:

type expression

The meaning of type is:

• 1: expand custom operators and output the expanded expression.
• 2: output the preorder traversal of the syntax tree.
• 3: expand custom operators, then evaluate the expression.

Output

For each query, output one line.

• For type 1, output the expanded expression.
• For type 2, output the preorder traversal of the syntax tree.
• For type 3, output the evaluated value, either 0 or 1.

Sample Input  Download

Sample Output  Download

Partial Judge Code

14949.c

Partial Judge Header

14949.h

Tags

Discuss

Description

Qsort, Linked List, Binary Tree, Tree Traversal, Expression Order, Syntax Tree, and Recursive Parsing

---

1. qsort

To use qsort, you have to include <stdlib.h>.

---

Usage

void qsort(void *array, size_t count, size_t size, comparison_fn_t compare);

---

qsort an int array

int compare_int(const void *a, const void *b)
{
    const int *va = (const int *)a;
    const int *vb = (const int *)b;

    return *va - *vb;
}

---

qsort a double array

int compare_double(const void *a, const void *b)
{
    const double *da = (const double *)a;
    const double *db = (const double *)b;

    return (*da > *db) - (*da < *db);
}

---

2. Linked List

Node Definition

typedef struct _Node {
    int data;
    struct _Node *next;
} Node;

---

Print the Content of the Linked List

void printList(Node *head)
{
    Node *temp;

    for (temp = head; temp != NULL; temp = temp->next) {
        printf("%d ", temp->data);
    }
}

---

Insert a Node After the Node Pointed by nd

Return 1 if insertion succeeds. Otherwise, return 0.

int insertNode(Node* nd, int data)
{
    if (nd != NULL) {

        Node* temp = (Node*)malloc(sizeof(Node));

        temp->data = data;
        temp->next = nd->next;
        nd->next = temp;

        return 1;
    }

    return 0;
}

---

Delete a Node After the Node Pointed by nd

Return 1 if deletion succeeds. Otherwise, return 0.

int deleteNode(Node* nd)
{
    if (nd != NULL) {
        Node* temp = nd->next;

        if (temp != NULL) {
            nd->next = temp->next;
            free(temp);

            return 1;
        }
    }

    return 0;
}

---

3. Binary Tree

Binary Tree Node Definition

typedef struct _node {
    int data;
    struct _node *left, *right;
} BTNode;

---

4. Tree Traversal

Traversal Type	Visit Order
Pre-order	Visit root, left subtree, and right subtree
In-order	Visit left subtree, root, and right subtree
Post-order	Visit left subtree, right subtree, and root

---

5. Expression Order

Expression Type	Order
Prefix	Operator, left operand, and right operand
Infix	Left operand, operator, and right operand
Postfix	Left operand, right operand, and operator

---

6. Syntax Tree

In a syntax tree, the internal nodes are operators, and the leaves are operands.

---

7. Recursive Evaluation of Prefix Expression

The following is pseudo code for evaluating a prefix Boolean expression.

int evalBoolExpr()
{
    char c = getchar();

    if (c is an operator) {

        op1 = evalBoolExpr();
        op2 = evalBoolExpr();

        return op1 c op2;

    } else if (c is a variable) {

        return the value of c;
    }
}

---

8. Grammar of Infix Expression with Parentheses

EXPR   = FACTOR | EXPR OP FACTOR
FACTOR = ID | (EXPR)

---

9. Syntax Tree Construction from Infix Expression

Suppose expr[] is an array of expression and pos is the current position, which is initially strlen(expr) - 1.

---

Create a New Tree Node

BTNode* makeNode(char c)
{
    int i;

    BTNode *node = (BTNode*)malloc(sizeof(BTNode));

    /* set node->data */
    node->data = c;

    node->left = NULL;
    node->right = NULL;

    return node;
}

---

Parse FACTOR

BTNode* FACTOR()
{
    char c;
    BTNode *node = NULL;

    if (pos >= 0) {

        c = expr[pos--];

        if (c is an ID) {

            node = makeNode(c);

        } else if (c == ')') {

            node = EXPR();

            if (expr[pos--] != '(') {
                printf("Error!\n");
                freeTree(node);
            }
        }
    }

    return node;
}

---

Parse EXPR

BTNode* EXPR()
{
    char c;

    BTNode *node = NULL;
    BTNode *right = NULL;

    if (pos >= 0) {

        node = right = FACTOR();

        if (pos > 0) {

            c = expr[pos];

            if (c is an operator) {

                node = makeNode(c);

                node->right = right;

                pos--;

                node->left = EXPR();
            }
        }
    }

    return node;
}

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss