소들의 알리바이 2

농부 존과 농부 존팜은 서로의 개인적인 갈등을 풀어 보려는 마음에 각자의 소들을 데리고 모닥불 주위에 둘러앉았다. 총 \(N\) (\(2 \leq N \leq 10^5\))마리의 소가 원형으로 앉아 있다. 소들을 데리고 각자의 농장으로 돌아가려던 순간, 두 농부는 한 가지 결정적인 실수를 깨달았다. 모든 소가 똑같이 생긴 데다 뒤섞여 버려서, 어떤 소가 어느 농부의 소인지 알아볼 수가 없는 것이다!

그리하여 \(N\)마리의 소는 두 농부에게 심문을 받기 위해 한 줄로 세워진다. 혼란 때문에, \(1\)부터 \(N\)까지 줄에 선 소들의 순서는 모닥불 주위의 원형 순서와 일치하지 않을 수 있다.

그런데 소들은 게임을 하고 싶어 한다. 자신이 어느 농부의 소인지 직접 답하는 대신, 원래 원에서 자신과 인접한 소들이 어느 농부의 소인지를 말한다. 또한 농부 존팜의 소들은 항상 거짓말을 하지만, 농부 존은 소들을 잘 길렀기 때문에 그의 소들은 항상 진실을 말한다는 것이 알려져 있다.

소들의 진술이 주어졌을 때, 농부 존에게 배정된 소들의 진술이 모두 참이고 농부 존팜에게 배정된 소들의 진술이 모두 거짓이 되도록 각 소를 농부 존 또는 농부 존팜에게 배정하는 것이 가능한가?

Problem credits: Chongtian Ma

SCORING

• 입력 3: \(C=0\)이고 \(N\le 10\)
• 입력 4: \(C=1\)이고 \(N\le 10\)
• 입력 5-8: \(C=0\)
• 입력 9-12: \(C=1\)

Problem credits: Chongtian Ma

첫째 줄에 독립적인 테스트 케이스의 수 \(T\) (\(1 \leq T \leq 1000\))와 정수 \(C\in \{0,1\}\) (구성을 출력할지 여부)가 주어진다.

각 테스트 케이스의 첫째 줄에 \(N\)이 주어진다.

다음 줄에 문자 J 또는 N으로 이루어진 길이 \(N\)의 문자열이 주어진다. \(i\)번째 문자는 소 \(i\)가 원에서 자신의 왼쪽 소가 농부 존의 소라고 주장하면 J, 농부 존팜의 소라고 주장하면 N이다.

다음 줄에 문자 J 또는 N으로 이루어진 길이 \(N\)의 문자열이 주어진다. \(i\)번째 문자는 소 \(i\)가 원에서 자신의 오른쪽 소가 농부 존의 소라고 주장하면 J, 농부 존팜의 소라고 주장하면 N이다.

모든 테스트에 걸친 \(N\)의 합이 \(5 \cdot 10^5\)를 넘지 않음이 보장된다.

각 테스트 케이스에 대해 YES 또는 NO를 출력한다.

추가로, \(C=1\)이고 답이 YES라면 구성을 설명하는 두 줄을 더 출력한다.

첫째 줄에는 모닥불 주위의 소들의 원형 순서를 나타내는 \(1\dots N\)의 순열 \(p_1, p_2, \dots, p_N\)을 출력한다. 여기서 \(i\)가 \(1 \dots N - 1\)일 때 소 \(p_i\)는 소 \(p_{i+1}\)의 왼쪽에 있고, 소 \(p_N\)은 소 \(p_1\)의 왼쪽에 있다.

둘째 줄에는 J와 N으로만 이루어진 문자열 \(b_1b_2\dots b_N\)을 출력한다. \(b_i\)가 J이면 소 \(p_i\)는 농부 존의 소이고, N이면 농부 존팜의 소이다.

유효한 구성이라면 무엇이든 정답으로 인정된다.

riseoj 작성

출처 올림피아드 > USACO > 2025-2026 > Second Contest > Silver