Description

Download the C++ reference.
You will see the file named "12534.cpp" but that's OK.
Just download the file and change the filename extension(副檔名) into "zip" then you can upzip the file and use the reference.
The link is below.

reference.zip

Input

Output

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss

Description

CSSA (資工系學會) is going to hold a BBQ party. The student enrollment is very high, yet the space is limited. So CSSA sorted the students with the special priority and the students with higher priority will be invited first. The priority is determined by the following rules:

1. The students who have paid the membership fee will have higher priority than those who haven't.
2. The junior students will have higher priority than the senior students.
3. The students who registered as a group will have higher priority than those who registered individually.

These rules are applied in the order of 1, 2, 3. Which means if two students have the same priority in rule 1, then we will compare their priority in rule 2, and if they still have the same priority, then we will compare their priority in rule 3. If they have the same priority in all the rules, then we will consider them as the same priority.

CSSA has all the registration information of the students in the order of registration time. Dogeon (鴿子) sorted them with the priority mentioned above. But then Stiff Waist Beast (挺腰獸) told Dogeon that he should sort the students with stable sorting algorithm. But Dogeon isn't sure if the sorting algorithm he used is stable or not. Help Dogeon to check if the sorting algorithm he used is stable or not.

Stable sorting algorithm: A sorting algorithm is said to be stable if and only if two elements with equal priority appear in the same order in the sorted output as they appear in the input array to be sorted.

• For C, you can use strcmp function to compare two strings.

#include <string.h>
int sameName(const char *a, const char *b) {
    return strcmp(a, b) == 0;
}

The function strcmp compares two strings lexicographically. It returns zero if the strings are equal, a negative value if the first string is lexicographically less than the second string, and a positive value if the first string is lexicographically greater than the second string.

• For C++, you can directly use the == operator to compare two std::string.

#include <string>
bool sameName(const std::string &a, const std::string &b) {
    return a == b;
}

• For those who write in C++, you can add the following code at the beginning of the main function to speed up the input and output:

ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);

Note: The purpose of ios_base::sync_with_stdio(false); is to unsynchronize the C and C++ standard streams. By default, all standard streams are synchronized, which means that C++ standard streams are tied to their respective C streams. After adding ios_base::sync_with_stdio(false);, you should use cin and cout for input and output. Do not use scanf and printf anymore.

Input

The first line of the input contains an integer \(t\), the number of sub-tasks. Followed by \(t\) sub-tasks. The description of each sub-task is as follows.

For each sub-task, the first line contains an integer \(N\), the number of students. Following \(N\) lines contain the information of the students \(a_i\) in the order of registration time. Following another \(N\) lines contain the information of the students \(b_i\) sorted by Dogeon.

\(N\)
\(a_1\)
\(a_2\)
\(\vdots\)
\(a_N\)
\(b_1\)
\(b_2\)
\(\vdots\)
\(b_N\)

The information of a student contains four parts: the name of the student \(S_i\), the grade of the student \(G_i\), the registration type of the student \(T_i\) (0 for individual, 1 for group), and the payment status of the student \(P_i\) (0 for unpaid, 1 for paid). The information is separated by a space.

\(S_i \quad G_i \quad T_i \quad P_i\)

Constraints

• \(1 \leq t \leq 10^5\)
• \(1 \leq N \leq 5 \times 10^6\)
• \(1 \leq \sum N \leq 5 \times 10^6\)
• \(1 \leq |S_i| \leq 20\)
• \(1 \leq G_i \leq 5\)
• Name of the student contains only lowercase and uppercase letters.
• None of the students have the same name.
• \(b_i\) is a permutation of \(a_i\), which means for each \(i\), there exists a unique \(j\) such that \(a_i = b_j\), and vice versa.
• \(b_i\) is sorted in the order of priority mentioned above.

1. For test case 1 ~ 4, \(\sum N \leq 10^3\)
2. For test case 5 ~ 8, \(\sum N \leq 2 \times 10^5\)
3. For test case 9 ~ 10, \(\sum N \leq 5 \times 10^6\), your time complexity might need to be \(O(N)\) to pass these two test cases.

Output

Output \(t\) lines. For each sub-task, output "YES" if the sorting algorithm is stable, and "NO" otherwise.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

"Run?"
"Who's running?"
"Running where?"
"And why?!" said Shadow sama. At the same time, Shadow sama spreads his mana all over Midgar Kingdom.

"Observe!"
"And witness for yourselves!"
"Supremely ultimate, almighty and unparalleled attack!"
"I..."
"...am..."

Beta (one of the Seven Shadows, higher-ups of Shadow Garden), who is keen on writing down feats of Shadow sama, is stunned by the sight of Shadow Sama's attack, and missed the chance to record it.

Beta has the map of Midgar Kingdom, which is a tree with \(N\) nodes, numbered from \(1\) to \(N\). Shadow Sama is at one of the nodes as he spreads his mana. With \(k\) unit of mana, Shadow Sama can cover the node he is at, and all the nodes that are at most \(k\) edges away from him.

Beta knows that Shadow Sama is so smart that he must have chosen the place he was at wisely, and spent the least amount of mana to cover the whole Midgar Kingdom. Sasuga Shadow Sama!

However, since Shadow Sama's attack is so breathtaking, Beta forgot to record the details of it. In order to demonstrate Shadow Sama's wisdom, you need to calculate the minimum amount of mana required for him to cover the whole Midgar Kingdom.

For the sample test case, we can draw the tree as shown below. When Shadow Sama is at node #1 (or node #5), he can cover all the nodes with 3 units of mana.

Input

The first line contains an integer \(N\), the number of nodes in the tree.

For the following \(N-1\) lines, each line contains two integers \(u_i\) and \(v_i\), indicating that there is an bidirectional edge between node \(u_i\) and node \(v_i\).

\(N\)
\(u_1 \quad v_1\)
\(u_2 \quad v_2\)
\(\vdots\)
\(u_{N-1} \quad v_{N-1}\)

Constraints

• \(1 \leq N \leq 10^5\)
• \(1 \leq u_i, v_i \leq N\)
• The input is a tree.

Output

Output contains one line with an integer, the minimum units of mana required to cover the whole Midgar Kingdom.

You don't have to print spaces or newlines at the end of the line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Forevernight is playing cards with his friend SugarHao in their new apartment Mèng Zhú public housing (孟竹國宅).

As a CS student, he wants to play it in a programmer way. He decides to write a program for the purpose of shuffling the cards. Moreover, since Forevernight is really famous in their department, more friends may come while he is shuffling cards, so sometimes he needs to insert new cards into the card stack, too.

In view of the fact that he's taking I2P(II) this semester, his another friend Jason(one of the TAs) commands that he should write the program in a C++ way.

Note: This is a patial judge problem. You're asked to implemet 5 functions in this problem.

1. Card* Construct(int N) - This function would create a linked list with N elements, each node (ie. card) contains a number given by testcase serially in one single line. (Noted that you should get the number from the input by std::cin or scanf on your own.) The function should return a pointer to the first element of the linked list. Warning: To improve your C++ skills, you should only use C++ operator new to allocate your Card node. We will use another function void Destruct(Card* head) using delete to deallocate the space.
2. void add(int idx, int num, Card* head) - This function should add a new card with number num before card idx.
3. void cut(int a, int b, Card* head) - This function should move cards whose index between a and a+b-1 ( [a, a+b) ) to the top of the card stack. Order of the cards inside the moved part shouldn't be changed.
4. void reverse(int a, int b, Card *head) - This function should reverse the order of cards whose index between a and a+b-1 ( [a, a+b) ).
5. void print(Card* head) - This function should print out the card list from top (index 0) to buttom (largest index), each number followed by a newline character '\n'.

Input

First line of input contains two integer \(n\), \(m\), representing # of cards in the beginning and # of operations.

Next line contains \(n\) integers \(c_1, c_2, \cdots, c_n\), representing the number on each card from the top (index 0) to the buttom (index n-1).

Each of the next \(m\) lines contains an operation. Operations begin with ADD, CUT or REVERSE.

• ADD idx num: Add a new card with number num before card idx.
• CUT a b: Move cards whose index between a and a+b-1 ( [a, a+b) ) to the top of the card stack. Order of the cards inside the moved part won't be changed. Index of a card means # of cards on the top of that card. It may change after operations.
• REVERSE a b: Reverse the order of cards whose index between a and a+b-1 ( [a, a+b) ).

Constraints

• \(1 \le n, m \le 10^4\)
• \(0 \le c_i \le 10^9\)
• \(0 \le a, b, idx\)
• In CUT operation, card with index = a+b-1 always exists.
• In REVERSE operation, card with index = a+b-1 always exists.

Operation in each testcase:

1. {ADD}
2. {CUT}
3. {REVERSE}
4. {ADD, CUT}
5. {ADD, CUT, REVERSE}
6. {ADD, CUT, REVERSE}
7. {ADD, CUT, REVERSE}
8. {ADD, CUT, REVERSE}

Output

Print out the card stack from top (index 0) to buttom (largest index), each number occupies one line.

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss