개발자 크루
박희진교수의 2024년 2학기 수업에 수강신청한 학생만 들어올 수 있습니다. 신청사유에 학번과 이름을 꼭 기재해 주기 바랍니다.
21년 재직자 대회 예선
[21년 재직자 대회 예선] 좌석 관리
- 난이도
- 3 단계
- 참가자
- 30 명
- 제출
- 68 명
- 정답률
- 52.94 %
언어별 시간/메모리
| 언어 | 시간 | 메모리 |
|---|---|---|
| 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.