Description

Niflheimr is playing cards with his friends. As a CS student, he wants to play in a programmer way. He decides to write a program for shuffling the cards. By the way, more friends may come while he is shuffling cards, so sometimes he needs to insert new cards into the card stack, too.

 

Hint: You can use linked list to implement.

Input

• 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.

• 1 ≤ n, m ≤ 10⁴
• Number on cards are non-negative integer and do not exceed 10⁷
• # of cards in the card stack will never exceeds 2*10⁴
• in CUT operation, card with index = a+b-1 always exists.

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

Tags

Discuss

Description

There are n people in a circle, numbered from 1 to n in clockwise direction. They are playing a game, and there will be m lucky people that can get the prizes.

Rules of the game:
1. Each prize has a lucky number.
2. Who is counted as the lucky number can get a prize.
3. If the lucky number is odd, count clockwise.
4. If the lucky number is even, count counterclockwise.
5. The student who gets a prize shall leave the circle.
6. After someone left the circle, if the new lucky number is odd, count from the next person, otherwise count from the previous person (in clockwise order).

For example: 
n = 8
m = 3
lucky number = 3 4 5

The sequence of getting prize is:
first number is 3, so count clockwise starting from 1: 1 2 3
second is 4, so we count from 2, and counterclockwise: 2 1 8 7
last number is 5, so we count from 8, and clockwise: 8 1 2 4 5

Then people 3, 7, 5 can get the prize.

Please use doubly circular linked list to solve this problem.

Input

The first line has two integer n and m, where n is the number of total people, and m is the number of prizes.

The second line has m positive number a_{1 ~} a_m.

testcases:

1. 1 <= m <= n <= 10000, 1 <= a_i <= n
2. 1 <= m <= n <= 10000, 1 <= a_i <= n
3. 1 <= m <= n <= 10000, 1 <= a_i <= n
4. 1 <= m <= n <= 1000000, 1 <= a_i <= 10000000, n*m <= 300000000
5. 1 <= k <= n <= 1000000, 1 <= a_i <= 10000000, n*m <= 300000000
6. 1 <= k <= n <= 1000000, 1 <= a_i <= 10000000, n*m <= 300000000

Output

The output has m lines, each line contains a number: who can get the prize.

Sample Input  Download

Sample Output  Download

Partial Judge Code

13129.c

Partial Judge Header

13129.h

Tags

Discuss

Description

In addition to Quicksort, merge sort is also a quite significant and classical sorting algorithm. Whereas partition is the most vital step of Quicksort, the most crucial step of merge sort  is to merge two sorted (non-decreasing, typically) sequences into a sorted one.

For instance, if we have two sorted sequence {1, 3, 8}, {2, 9}, then the merged sequence would be {1, 2, 3, 8, 9}.

This is a partial-judged problem. Please implement the following function:

Where node is declared as:

 

Input

The function would be called with the heads of the two sorted linked list.

It's guaranteed that the sum of the length of the linked lists would not exceed 2000000.

Output

It should return the head of the merged linked list.

Sample Input  Download

Sample Output  Download

Partial Judge Code

13829.c

Partial Judge Header

13829.h

Tags

Discuss

Description

You must be familiar with Josephus problem. In case your impression is faded, it’s a game that \(n\) people (say \(1,2,\dots,n\)) in a circle and in each round \(k\) people are repeatedly skipped and the next people is eliminated.

In this problem, we are curious about the order people eliminated.

Input

There would be two integers \(n,k\) in a line.

Constraints

\(1 \leq n \leq 10^4\)
\(0 \leq k \leq 10^9\)

Output

For each round, please print the order people eliminated. The order should be printed in a line, and there should be a space after each number.

DO NOT to print '\n' at the end of output.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Procat(破貓), AKA God of cycling is planning for a trip. As a student in the CS department, he decided to use a linked list to represent his trip. However, he accidentally pointed the last node to the body of the linked list, making some of the linked lists contain a cycle. Help him find out if there is a cycle in a given linked list.

Procat plans to visit \(N\) viewpoints. Numbered from \(0\) to \(N-1\). He will start from viewpoint \(0\) and visit viewpoint \(c_i\) after visiting viewpoint \(i\), until \(c_i = -1\). Each viewpoint contains a value \(a_i\).

• Definition for singly linked list:

  typedef struct ListNode {
      int val;
      struct ListNode *next;
  } ListNode;

• This is a partial judge problem. Input and output are handled by 14210.c. All you have to do is implement the function
  bool hasCycle(ListNode *head), which returns true if there is a cycle in the given linked list, otherwise returns false.

• You should not modify the given linked list, or you will get a wrong answer.

Input

There are multiple subtasks in each testcase. The first line of the input contains an integer \(T\) indicating the number of subtasks. For each subtask, there will be three lines, formatted as following:

• One integer \(N\) indicating the number of nodes.
• \(N\) integers \(c_i\) indicating the next node of node \(i\).
• \(N\) integers \(a_i\) indicating the val stored in node \(i\).

\(N\)
\(c_0 \quad c_1 \quad c_2 \quad \ldots \quad c_{N-1}\)
\(a_0 \quad a_1 \quad a_2 \quad \ldots \quad a_{N-1}\)

It’s guaranteed that all nodes can be reached from node 0 in each testcase.

subtask 1:

subtask 2:

subtask 3:

Constraints

\(1 \le T \le 10^4\)
\(1 \le N \le 10^7\)
\(1 \le \sum N \le 10^7\)
\(-1 \le c_i < N\)
\(-10^9 \le a_i \le 10^9\)

• For \(33\%\) of the testcases, \(a\) is unique for each node.
• For \(67\%\) of the testcases, there is no additional constraint.

Output

For each subtask, output one line containing “Yes” if there is a cycle in the given linked list, otherwise output “No”. Print a newline character after each line.

Since this is a partial judge problem, you don’t have to worry about the output format.

Sample Input  Download

Sample Output  Download

Partial Judge Code

14210.c

Partial Judge Header

14210.h

Tags

Discuss