시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 1024 MB | 95 | 28 | 25 | 37.879% |
올바른 괄호 문자열(VPS)은 다음과 같이 정의한다.
S
가 VPS라면 (S)
도 VPS이다.S
와 T
가 VPS라면 ST
도 VPS이다.예를 들어 "(())()
", "()()()
", "(()())
” 등은 VPS이고, "())(()
", "(
", "(()()()
" 등은 VPS가 아니다.
VPS를 좋아하는 태수는 길이가 $N$인 VPS $S$를 선물 받았다. 하지만 태수의 위시리스트에 담겨있던 VPS는 $T$였기에, $S$의 두 문자를 바꾸는 작업을 최대 $N$번 해서 $T$로 만들고 싶었다. 하지만 VPS를 좋아하는 태수는 다음과 같은 조건들을 만족할 때만 두 원소를 바꾸기로 했다.
태수를 위해 $S$를 $T$로 바꾸는 방법을 알려주자. 답이 반드시 존재함을 증명할 수 있다.
첫째 줄에 테스트케이스의 개수 $C$가 주어진다. $(1 \leq C \leq 5 \times 10^5)$
각 테스트케이스 별로 입력은 다음과 같이 주어진다.
첫째 줄에 정수 $N$이 주어진다. $(1 \leq N \leq 10^6)$
둘째 줄에 길이가 $N$인 VPS $S$가 주어진다.
셋째 줄에 길이가 $N$인 VPS $T$가 주어진다.
모든 테스트케이스의 $N$의 합은 $10^6$을 넘지 않는다.
각 테스트케이스 별로 다음과 같이 출력한다.
첫째 줄에 작업 횟수 $X$ $(0 \leq X \leq N)$를 출력한다.
둘째 줄부터 $X$줄에 걸쳐, 바꾸는 두 원소의 인덱스 $L$ $R$ 을 작업 순서에 맞춰 출력한다.
반드시 작업 횟수가 최소가 될 필요는 없다.
2 6 (())() ()(()) 4 ()() (())
2 4 5 2 3 3 2 3 2 3 2 3
University > 고려대학교 > 2021 고려대학교 프로그래밍 경시대회 (KCPC) > Div. 2 F번
University > 고려대학교 > 2021 고려대학교 프로그래밍 경시대회 (KCPC) > Div. 1 C번