시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB277550.000%

문제

이상한 청소기를 만드는 회사 사장 실버가 또 새로운 청소기 모델 Silver-X 를 발표했다! 이번 청소기는 강한 흡입력이 특징인데, 리모컨의 버튼을 한 번 누르면 거리에 상관없이 양옆 방향의 모든 물체가 청소기를 향해 거리 1만큼 이동한다. 거리가 1이었던 물체들은 질량-에너지 등가 원리에 따라 엄청난 에너지를 방출하며 사라진다. (심지어 그 물체가 다른 Silver-X 청소기여도 말이다!) 따라서 이 과정을 거치면 거리가 $m$이었던 물체와의 거리는 $m-1$이 된다. 하지만 만약 양옆 중 한쪽이라도 물체가 없다면, 청소기는 청소기 자체의 힘을 이기지 못하고 엄청난 에너지를 방출하며 사라진다. 이때 다른 모든 물체는 이동하거나 사라지지 않으며, 그 청소기 하나만 사라져버린다.

어차피 제품을 팔기는 글렀다는 사실을 알고 있는 실버는 알고리즘의 마술사인 당신과 함께 마술 공연을 하여 돈을 벌기로 했다.

무대에는 $n$개의 물체들이 일렬로 놓여 있다. 이 물체는 새로운 청소기 모델 Silver-X 거나 폭탄이다. 이웃한 두 물체 사이의 거리는 모두 1이다. 당신은 $n$개의 물체들을 조작할 수 있는 리모컨 $n$개를 가지고 있다. 리모컨의 번호는 1번부터 시작하며, 왼쪽부터 순서대로 매겨져 있다. 만약 Silver-X 와 연결된 리모컨의 버튼을 누른다면 Silver-X 가 정상적으로 작동하여 주변 물체들을 빨아들일 것이다. 하지만 폭탄과 연결된 리모컨의 버튼을 누른다면 폭탄이 터져버릴 것이다. 또한, 이미 사라진 물체와 연결된 리모컨의 버튼을 누른다면 아무 일도 일어나지 않지만, 성난 관중들이 당신에게 돌을 던질 것이다.

이 공연의 목표는 폭탄을 터뜨리는 일 없이, 또 관중들이 돌을 던지는 일 없이 $n$개의 물체를 모두 사라지게 하는 것이다. 따라서 폭탄을 처리하기 위해서는 반드시 청소기를 이용하여 흡수해야 한다. 다음은 5개의 물체 중 2번과 4번이 청소기일 때의 예시다.

2번, 4번, 4번 리모컨을 순서대로 누른 경우 (성공) 2번, 2번, 4번 리모컨을 순서대로 누른 경우 (실패)

청소기와 폭탄이 일렬로 배치된 상태가 주어질 때, 공연을 어떻게 해야 성공적으로 마칠 수 있는지 구하는 프로그램을 작성해보자!

입력

첫 번째 줄에 청소기와 폭탄이 일렬로 배치된 상태가 길이 $n$인 문자열로 주어진다. 청소기는 X, 폭탄은 .으로 표시한다.

출력

공연을 성공적으로 마칠 수 없다면 첫 번째 줄에 -1을 출력한다.

공연을 성공적으로 마칠 수 있다면 첫 번째 줄에 리모컨 버튼을 누르는 횟수 $k$를 출력한다.

두 번째 줄에 눌러야 하는 리모컨의 번호 $k$개를 공백으로 구분하여 순서대로 출력한다.

$k$를 최소화할 필요는 없으며, 가능한 방법이 여러 가지인 경우 아무거나 한 가지만 출력한다.

제한

  • $1 \le n \le 1\,000\,000$
  • $1 \le k \le 1\,000\,000$

예제 입력 1

.X...X...

예제 출력 1

5
2 6 6 6 6

예제 입력 2

X.X

예제 출력 2

-1

예제 입력 3

...X.....X..

예제 출력 3

7
4 10 10 4 4 10 4

출처

Contest > BOJ User Contest > 실버컵 > 제1회 실버컵 D번

  • 문제를 만든 사람: cozyyg
  • 문제를 검수한 사람: jh05013