시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 983 | 154 | 119 | 28.744% |
창영이는 1학년 때 숙제로 했던 이중 연결 리스트 소스를 상근이에게 생일 선물로 보내주었다. 상근이는 드디어 자신이 원하던 기능이 있는 소스를 받게 되어서 매우 기뻤다. 상근이는 하루종일 이 리스트를 가지고 놀려고 한다.
리스트에는 총 N개의 노드가 포함되어 있고, 가장 왼쪽 노드가 1번이며 나머지는 오른쪽으로 갈 수록 1씩 번호가 증가한다. 리스트가 수행할 수 있는 연산은 아래와 같이 2가지이다.
A) 노드 X를 노드 Y의 앞으로 이동
B) 노드 X를 노드 Y의 뒤으로 이동
아래 그림은 노드가 6개인 이중 연결 리스트의 모습이다.
여기에 "A 1 4" 연산을 수행하면 아래와 같이 된다. (노드 1을 노드 4의 앞으로 이동)
그 다음, "B 3 5" 연산을 수행하면 아래 그림과 같은 모습이 된다. (노드 3을 노드 5의 뒤로 이동)
리스트를 가지고 다 논 다음에는 처음 상태로 다시 만들어야 한다. 따라서, 상근이는 리스트에 연산을 입력할 때 마다 종이에 적어두었다.
상근이가 입력한 연산이 모두 주어졌을 때, 처음 상태로 만들기 위해 리스트가 수행해야 하는 연산을 구하는 프로그램을 작성하시오. 이때, 연산을 되도록 적게 사용해야 한다.
첫째 줄에 노드의 수 N과 연산의 수 M이 주어진다. (2 ≤ N ≤ 500,000, 0 ≤ M ≤ 100,000)
다음 M개 줄에는 상근이가 입력한 연산이 문제 설명에 나온 형식으로 주어진다.
첫째 줄에 처음 상태로 만들기 위해서 필요한 연산의 최솟값을 출력한다. 이 값을 K라고 한다.
다음 K개 줄에는 리스트가 수행해야 하는 연산을 순서대로 출력한다.
2 1 A 2 1
1 A 1 2
4 3 B 1 2 A 4 3 B 1 4
2 A 1 2 B 4 3
6 5 A 1 4 B 2 5 B 4 2 B 6 3 A 3 5
3 A 4 5 B 6 5 A 2 3
Contest > Croatian Open Competition in Informatics > COCI 2006/2007 > Contest #3 6번