개발자 크루

hsat 코딩 공부방

hsat을 위한 기초지식부터 코딩테스트 준비까지!

challenge LV.3

썸네일

[21년 재직자 대회 예선] 좌석 관리

난이도
3 단계
참가자
0 명
제출
0 명
정답률
0.00 %
언어별 시간/메모리
언어별 시간/메모리 표
언어 시간 메모리
JavaScript 5초 1024MB
C 5초 1024MB
C++ 5초 1024MB
Java 5초 1024MB
Python 5초 1024MB

현대자동차그룹에서 사내 식당 매니저로 일하는 기항이는 점심 시간에 맞춰 일을 하고 있다. 오늘 일은 사람들이 사회적 거리두기를 잘 지키면서 식당 좌석에 앉도록 상황을 관리하는 일이다.


현재 식당에는 좌석 N×M개가 N행 M열로 나열되어 있는데, 각 좌석에는 (1,1)에서 (N,M)로 좌표가 배정되어 있다. x행 y열에 있는 좌석의 좌표는 (x,y)이다.


점심 시간에는 많은 사람들이 식당을 드나든다. 사번이 id인 어떤 사원이 식당에 왔다면, 다음 조건에 맞춰 이 사원을 위한 좌석을 배정해준다.


현재 K개의 좌석이 차 있고, 이 중 i번째 좌석은 (xi,yi)라고 하자. 이 상황에서 어떤 좌석 (X,Y)의 안전도 DX, Y는 이다.

즉, 다른 사람까지의 거리 중 가장 가까운 거리다. 단, 방역 수칙에 따르면 사람들은 상하좌우에 바로 붙어 앉을 수 없다.




또한 아래의 그림에서 처럼 경계 밖은(좌, 하) 고려하지 않는다.




기항이는 현재 비어있는 좌석 (X,Y) 중에서 방역 수칙을 고려하는 동시에, 안전도가 가장 높은 좌석을 새로 들어오는 사람에게 배정해준다.

배정해줄수 있는 좌석 중 안전도가 가장 높은 좌석이 여럿 있을 수 있다. 이 때는 그 중에서 X가 가장 낮은 좌석을, X도 같다면 Y가 가장 낮은 좌석을 배정해 준다. 특수하게, 현재 모든 좌석이 비어있다면 (1,1)이 배정된다.


사번이 id인 어떤 사원이 식당에서 떠난다면, 그 사원이 있던 자리는 빈 자리가 된다. 각 사원들에게 주어지는 점심 식사는 단 한번이므로, 여러 번 점심을 먹을 수는 없다. 그러므로 이미 점심을 먹은 사원은 돌려보내야 한다.


이외에도 각 직원의 점심 식사 여부에 따른 처리가 요구되는데, 출력 형식을 참고하여 모든 작업을 적절히 처리해보자.

제약조건

1 ≤ N, M ≤ 20

1 ≤ Q ≤ 3×104

1 ≤ id ≤ 104

입력형식

첫 번째 줄에 세 자연수 N, M, Q가 주어진다.

다음 Q개의 줄에는 각 줄마다 처리해야 하는 작업이 In {id} 혹은 Out {id}의 형태로 주어진다.

출력형식

Q개의 줄에 걸쳐서, i번째 줄에는 i번째 작업을 처리한 결과를 출력한다.

각 작업마다 출력하는 방식은 다음과 같다.


작업이 In {id}로 주어졌을 때

- 사번이 id인 사원이 현재 좌석에 앉아 밥을 먹고 있다면, {id} already seated.를 출력한다.

- 사번이 id인 사원이 이미 밥을 먹고 떠났다면, {id} already ate lunch.를 출력한다.

- 사번이 id인 사원이 자리가 가득 차서 좌석을 배정받는 데 실패했다면, There are no more seats.를 출력한다.

- 사번이 id인 사원이 성공적으로 좌석 (x,y)에 앉았다면, {id} gets the seat ({x}, {y}).를 출력한다.


작업이 Out {id}로 주어졌을 때

- 사번이 id인 사원이 아직 점심을 먹지 못했다면, {id} didn't eat lunch.를 출력한다.

- 사번이 id인 사원이 이미 밥을 먹고 좌석을 떠났다면, {id} already left seat.를 출력한다.

- 사번이 id인 사원이 좌석 (x,y)에 앉아 있었다면, {id} leaves from the seat ({x}, {y}).를 출력한다. 이 사원은 점심을 먹은 상태로 기록된다.

입력예제1

1 3 10
Out 1
In 1
In 2
In 2
In 3
Out 2
In 3
Out 2
Out 1
In 1
출력예제1

1 didn't eat lunch.
1 gets the seat (1, 1).
2 gets the seat (1, 3).
2 already seated.
There are no more seats.
2 leaves from the seat (1, 3).
3 gets the seat (1, 3).
2 already left seat.
1 leaves from the seat (1, 1).
1 already ate lunch.
입력예제2

4 4 7
In 7
In 6
In 5
In 4
In 3
In 2
In 1
출력예제2

7 gets the seat (1, 1).
6 gets the seat (4, 4).
5 gets the seat (1, 4).
4 gets the seat (4, 1).
3 gets the seat (2, 2).
2 gets the seat (3, 3).
There are no more seats.