PVHOI 2.0 - Bài 3: Biến đổi dãy ngoặc

View as PDF



Author:
Problem type
Allowed languages
C, C#, C++, Clang, Clang++, Cobol, D, Groovy, Haskell, Java, JS, Kotlin, Lua, Node JS, ObjectiveC, OCaml, Output, Pascal, PHP, Prolog, Pypy, Pypy 3, Ruby, Rust, Scala, Swift
Points: 60 (p) Time limit: 1.75s Memory limit: 1G Input: stdin Output: stdout

Dãy ngoặc là một dãy chỉ gồm các kí tự mở ngoặc ( và đóng ngoặc ). Dãy ngoặc đúng là một dãy ngoặc được xây dựng dựa trên quy tắc sau:

  • Dãy ngoặc rỗng là một dãy ngoặc đúng.
  • Nếu \(A\) là một dãy ngoặc đúng, thì (\(A\)) là một dãy ngoặc đúng.
  • Nếu \(A\)\(B\) là hai dãy ngoặc đúng thì \(AB\) cũng là dãy ngoặc đúng.

Ví dụ, (()), ()()()(()) là các dãy ngoặc đúng; còn )( hay (() thì không.

Bạn được cho một xâu kí tự \(s\) là một dãy ngoặc đúng cùng dãy \(q\) số \(p_1, p_2, \ldots, p_q\). Bạn cần thực hiện lần lượt \(q\) thao tác. Tại thao tác thứ \(i\), bạn cần làm những việc sau:

  • Thay đổi kí tự thứ \(p_i\) của \(s\) (từ ( sang ) hoặc ngược lại).
  • Tìm vị trí \(a_i\) là vị trí nhỏ nhất sao cho nếu thay đổi kí tự ở vị trí \(a_i\) (từ ( sang ) hoặc ngược lại) thì xâu kí tự \(s\) trở thành dãy ngoặc đúng.
  • In ra vị trí \(a_i\) vừa tìm được và thay đổi kí tự ở vị trí này.

Chú ý rằng, ở bất kì thao tác nào, bạn bắt đầu khi xâu \(s\) đang là dãy ngoặc đúng. Do đó, việc thay đổi kí tự thứ \(p_i\) khiến \(s\) bây giờ chắc chắn không phải dãy ngoặc đúng, và ta dễ dàng chứng minh được vị trí \(a_i\) cần tìm ở trên là luôn tồn tại. Khi thay đổi kí tự ở vị trí \(a_i\), \(s\) trở lại là dãy ngoặc đúng.

Input

  • Dòng đầu tiên chứa hai số nguyên \(n\)\(q\) \((1 \leq n \leq 1000000, 1 \leq q \leq 600000)\), lần lượt là độ dài của dãy ngoặc \(s\) và số thao tác bạn cần thực hiện.

  • Dòng thứ hai chứa xâu kí tự \(s\) là một dãy ngoặc đúng độ dài \(n\).

  • Dòng thứ ba chứa \(q\) số nguyên \(p_1, p_2, \ldots, p_q\) \((1 \leq p_q \leq n)\) mô tả các thao tác cần thực hiện.

Output

  • In ra \(q\) số nguyên \(a_1, a_2, \ldots, a_q\) là các vị trí tìm được ở các thao tác. Các số cần được viết trên một dòng, ngăn cách với nhau bởi dấu cách.

Scoring

Bộ test của bài được chia làm các subtask như sau:

  • Subtask \(1\) (\(14.4\) điểm): \(n \leq 500\)\(q \leq 300\)
  • Subtask \(2\) (\(15.6\) điểm): \(n \leq 7000\)\(q \leq 4200\)
  • Subtask \(3\) (\(14.4\) điểm): \(n \leq 200000\)\(q \leq 120000\)
  • Subtask \(4\) (\(15.6\) điểm): \(n \leq 1000000\)\(q \leq 600000\)

Điểm tối đa của bài là \(60\) điểm.

Example

Test 1

Input
6 3
((()))
4 3 1
Output
2 2 1
Note

Trong ví dụ trên, ban đầu dãy ngoặc \(s\)((())). Các thao tác diễn ra như sau:

  • Thao tác đầu tiên: Sau khi thay đổi kí tự ở vị trí \(p_1 = 4\), \(s\) trở thành (((()). Để \(s\) trở lại là dãy ngoặc đúng, bạn cần thay đổi kí tự ở vị trí \(a_1 = 2\). Khi đó \(s\) trở thành ()(()).
  • Thao tác tiếp theo: Sau khi thay đổi kí tự ở vị trí \(p_2 = 3\), \(s\) trở thành ())()). Để \(s\) trở lại là dãy ngoặc đúng, bạn cần thay đổi kí tự ở vị trí \(a_2 = 2\). Khi đó \(s\) trở thành (()()).
  • Thao tác cuối cùng: Sau khi thay đổi kí tự ở vị trí \(p_3 = 1\), \(s\) trở thành )()()). Để \(s\) trở lại là dãy ngoặc đúng, bạn cần thay đổi kí tự ở vị trí \(a_3 = 1\). Khi đó \(s\) trở thành (()()).

Comments

There are no comments at the moment.