5회 문제풀이 05 / ABC 213 C - Reorder Cards
ABC 213 C - Reorder Cards
【문제 개요】
H행 W열의 칸이 있습니다. 각 칸은 (i, j)로 표현됩니다. 여기서 i는 위에서부터의 행 번호, j는 왼쪽에서부터의 열 번호입니다.(1 ≤ i ≤ H, 1 ≤ j ≤ W)
N장의 카드가 칸위에 놓여있습니다. k번째 카드는 (Ak, Bk)칸에 놓여 있습니다.
이 카드에 대해서, 이하와 같은 2종류의 조작을 가능한 만큼 수행합니다.
- 숫자 카드가 없는 행은 카드와 함께 제거하고 남은 카드를 위로 채웁니다.
- 숫자 카드가 없는 열은 카드와 함께 제거하고 남은 카드를 왼쪽으로 채웁니다. 이 작업을 수행한 후, 각 카드의 새로운 위치(행과 열)를 구하세요.
힌트 : 좌표 압축(coordinate compression) 기법
【전제】
- 1 ≤ H, W ≤ 10⁹
- 1 ≤ N ≤ min(10⁵, HW)
- 1 ≤ Aᵢ ≤ H
- 1 ≤ Bᵢ ≤ W
- 모든 (Aᵢ, Bᵢ)쌍은 서로 다르다.
- 입력에 포함된 모든 수치는 정수이다.
【입력 형태】
1
2
3
4
H W N
A₁ B₁
...
Aₙ Bₙ
【출력 형태】
N개의 줄에 걸쳐, k번째 줄에 k번째 카드의 새로운 위치를 나타내는 두 개의 정수의 좌표를 공백으로 구분해서 Cᵢ Dᵢ로 출력하라.
【예시】
입력 예 1
1
2
3
4 5 2
3 2
2 5
출력 예 1
1
2
2 1
1 2
아무것도 적혀있지 않은 카드를 *로 표현한다면 최초 카드의 배치는 아래와 같습니다.
1
2
3
4
*****
****2
*1***
*****
조작 완료후, 카드의 배치는 아래와 같이 됩니다.
1
2
*2
1*
1이 적혀있는 카드는 위에서부터 2행째, 왼쪽에서 1행째에 있으며 2가 적혀있는 카드는 위에서부터 1행째, 왼쪽에서 2행째에 있다.
입력 예 2
1
2
3
4
5
6
7
8
9
10
11
1000000000 1000000000 10
1 1
10 10
100 100
1000 1000
10000 10000
100000 100000
1000000 1000000
10000000 10000000
100000000 100000000
1000000000 1000000000
출력 예 2
1
2
3
4
5
6
7
8
9
10
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 10
このポストは作成者の CC BY 4.0 ライセンスによって保護されます。