¿La página no carga? Prueba haciendo clic aquí.
Placeholder

#10450

무지개 정렬 20s 2048MB

Problemas

당신의 친구 찰스가 도전을 내밀었다. 그는 \mathbf{N}장의 카드를 탁자 위에 놓고 자신이 고른 순서로 한 줄로 배열한다. 각 카드는 하나의 색을 가지며, 하나의 색이 한 장 이상 존재할 수도 있다.

찰스는 이어서, 자신의 배열 순서를 바꾸지 않은 채 각 카드에 양의 정수를 하나씩 적되 다음을 만족하라고 한다:

  1. 카드를 왼쪽에서 오른쪽으로 읽을 때, 적힌 정수들이 비내림차순(감소하지 않음)이어야 한다.
  2. 같은 색의 카드에는 같은 정수를 적어야 한다.
  3. 다른 색의 카드에는 서로 다른 정수를 적어야 한다.

마지막으로 찰스는 적힌 정수의 오름차순으로 색들을 나열하고 싶어 한다. 예를 들어, 파란 카드에 2, 빨간 카드에 5, 초록 카드에 3을 적었다면 색의 순서는 파랑, 초록, 빨강이 된다.


Entrada

입력의 첫 줄에는 테스트 케이스 개수 \mathbf{T}가 주어진다. 이어서 \mathbf{T}개의 테스트 케이스가 주어진다.

각 테스트 케이스는 정수 \mathbf{N}이 주어지는 한 줄로 시작한다. 다음 줄에는 \mathbf{N}개의 정수 \mathbf{S_1}, \mathbf{S_2}, \dots, \mathbf{S_N}이 주어지며, \mathbf{S_i}는 왼쪽에서 i-번째 카드의 색을 나타낸다.


Salida

각 테스트 케이스마다 한 줄을 출력하라. 형식은 Case #x: y이며, x는 테스트 케이스 번호(1부터 시작)이고 y는 요청한 순서대로, 각 색을 한 번씩 나열한 결과이다. 주어진 카드에 규칙을 모두 만족하도록 정수를 적는 것이 불가능하다면, y는 대신 IMPOSSIBLE이어야 한다.


Ejemplo 

2
4
3 8 8 2
5
3 8 2 2 8
Case #1: 3 8 2
Case #2: IMPOSSIBLE
샘플 케이스 #1에는 4장의 카드에 3가지 색이 있다. 가능한 해 중 하나는 순서대로 1, 2, 2, 3을 적는 것이다. 같은 정수(2)가 색 8의 두 카드에 모두 적힌다는 점에 주의하라. 그러면 색의 순서는 3, 8, 2가 된다. 샘플 케이스 #2에서 색 8의 카드에 적힌 정수를 c_8, 색 2의 카드에 적힌 정수를 c_2라고 하자. c_2 \gt c_8이면 오른쪽 끝 두 카드의 정수가 비내림차순이 아니다. c_2 \lt c_8이면 왼쪽에서 두 번째와 세 번째 카드에서 그 문제가 발생한다. 마지막으로 c_8 = c_2는 규칙상 허용되지 않는다. 따라서 이 경우 정수를 유효하게 적는 방법이 없다.

Fuente

GCJ 2023a C

Debes iniciar sesión para escribir código.