2754 - I2P(II) 2023_Kuo

#	Problem	Pass Rate (passed user / total user)
13129	Prize!
13829	Linked List Mergence

13129 - Prize!

Status | Limits Submit

	Time	Memory
Case 1	1 sec	32 MB
Case 2	1 sec	32 MB
Case 3	1 sec	32 MB
Case 4	1 sec	32 MB
Case 5	1 sec	32 MB
Case 6	1 sec	32 MB

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 input 1
8 3
3 4 5


sample input 2
7 5
3 3 3 3 3

Sample Output Download

sample output 1
3
7
5


sample output 2
3
6
2
7
5

Partial Judge Code

13129.c

Partial Judge Header

13129.h

13829 - Linked List Mergence

Status | Limits Submit

	Time	Memory
Case 1	1 sec	32 MB
Case 2	1 sec	32 MB
Case 3	1 sec	32 MB
Case 4	1 sec	32 MB
Case 5	1 sec	32 MB
Case 6	2 sec	64 MB
Case 7	2 sec	64 MB
Case 8	2 sec	64 MB
Case 9	2 sec	64 MB
Case 10	2 sec	64 MB

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:

node *merge_linked_list(node *, node *);

Where node is declared as:

typedef struct _node {

int val;

struct _node *next;

} node;

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

1 2 3 8 9
1 2 4 5 6 7
0 1 2 4 5 6
0 1 1 1 3 3 4

Partial Judge Code

13829.c

Partial Judge Header

13829.h