DMPG '18 G1 - Musical Chairs - DMOJ: Modern Online Judge

DMPG '18 G1 - Musical Chairs

Points: 10 (partial)

Time limit: 1.4s

Memory limit: 256M

Author:

Problem type

There are $N$ $N$ chairs in a circle. Exactly $K$ $K$ of these chairs are empty and there are $K+1$ $K + 1$ students numbered from $1$ $1$ to $K+1$ $K + 1$ standing at some of these chairs. Every second, each student moves forward by one chair. In particular, if they are currently standing by chair $N$ $N$ , then they will move to chair $1$ $1$ after. If a student reaches an empty chair, including at the very beginning, they will sit down for the remaining time. Who will be the last standing student?

It is guaranteed that every student begins at a different chair.

Edit: The test data has been fixed.

Constraints

For all subtasks:

All the indices in the input will be between $1$ $1$ and $N$ $N$ inclusive.

Subtask 1 [30%]

$1 \le K < N \le 5\,000$ $1 \leq K < N \leq 5 000$

Subtask 2 [50%]

$1 \le K < N \le 200\,000$ $1 \leq K < N \leq 200 000$

Subtask 3 [20%]

$1 \le K < N \le 1\,000\,000$ $1 \leq K < N \leq 1 000 000$

Input Specification

The first line will have two space-separated integers, $N$ $N$ and $K$ $K$ .
The next line will have $K$ $K$ space-separated integers representing the indices of the empty chairs.
The third line will have $K+1$ $K + 1$ space-separated integers. The $i^\text{th}$ $i^{th}$ integer is the chair at which student $i$ $i$ begins at.

Output Specification

Output a single integer, the index of the last standing student.

Sample Input

Copy

7 2
2 1
6 5 4

Sample Output

Copy

Comments

8

DarthVader336 commented on May 13, 2018, 8:04 p.m.

Okay. Thanks wleung_bvg very much!

0

DarthVader336 commented on May 13, 2018, 4:30 p.m.

Will that happen?

1

DarthVader336 commented on May 13, 2018, 4:30 p.m. ← edited →

What should I output if more than one students remain standing in the end and sit down at the same time? Will that happen?

4

wleung_bvg commented on May 13, 2018, 6:11 p.m. ← edited →

Since there is exactly 1 less chair than students, if the last 2 students were to sit down at the same time, then they must be sitting down at the same chair. Since each student only move forward exactly one spot each second, then for this to happen, they would have had to start at the same place. Since the problem guarantees that each student starts at a different location, we know that this situation is impossible.

1

DarthVader336 commented on May 13, 2018, 7:04 p.m. ← edited →

What if the input is:

4 2

2 4

1 2 3?

2nd student will immediately sit down. After one round, 1 sit on 2 and 3 sit on 4.

For clarification, if a student sit on a chair, will that chair count as non-empty?

3

wleung_bvg commented on May 13, 2018, 7:55 p.m.

Student 1 cannot sit on chair 2 since student 2 is already sitting there.