문자열과 순열
시간 제한1초메모리 제한1024 MB
숨겨진 순열 p가 있을 때, 한 번의 질문으로 최소 개수의 인덱스 쌍 대소 관계를 물어 t[p_i] = s_i인 문자열 t를 복원합니다.
문제
길이가 n인 소문자 영문자로 이루어진 문자열 s_1 s_2 ... s_n이 주어진다. 심사위원은 순열 p_1, p_2, ..., p_n을 정하고, s의 i번째 문자를 t의 p_i번째 위치에 놓아 새 문자열 t를 만들었다. 문자열 t를 구하라.
이를 위해 k개의 인덱스 쌍으로 이루어진 질문을 한 번 할 수 있다. 쌍 (a_i, b_i) (1 ≤ i ≤ k, 1 ≤ a_i < b_i ≤ n)에 대해 p_{a_i} < p_{b_i}가 성립하는지 알 수 있다.
질문에 포함되는 쌍의 개수 k는 최소로 해야 한다. 검사 프로그램은 적응적이어서, 어떤 쌍을 물어보는지에 따라 답이 달라질 수 있다. 따라서 해답은 가능한 모든 순열 p에 대해 문자열 t를 올바르게 복원해야 한다.
힌트
첫 번째 예제에서는 쌍 (1, 2)에 대해 질문하고 답으로 1을 받는다. 이는 p_1 < p_2를 뜻하므로 순열은 p = 1 2이고, 문자열은 ab이다.
두 번째 예제에서는 쌍 (1, 2)에 대해 질문하고 답으로 0을 받는다. 이는 p_1 >= p_2를 뜻하므로 순열은 p = 2 1이고, 문자열은 ba이다.
세 번째 예제에서는 어떤 쌍도 묻지 않고 답 문자열 qqq를 바로 출력한다.
네 번째 예제에서 숨겨진 순열은 2 3 1이었다.