Mã hóa dãy ngoặc

View as PDF

Submit solution


Points: 400 (partial)
Time limit: 1.0s
Memory limit: 64M
Input: stdin
Output: stdout

Author:
Problem types
  • Giả sử ta có một chuỗi ngoặc đơn đúng, ta gọi chuỗi này là ~S~, khi đó ~S~ có hai cách giải mã sau đây:

    • Cách 1: ~S~ sẽ được mã hóa dưới dạng ~P=p_1,p_2,...,p_n~. Trong đó ~p_i~ là số lượng ngoặc đơn trái "(" đứng trước ngoặc đơn phải ")" thứ ~i~ tính từ trái.

    • Cách 2: ~S~ sẽ được mã hóa dưới dạng ~W=w_1,w_2,...,w_n~. Gọi ~r~ là vị trí dấu ngoặc đơn ")" thứ ~i~ tính từ trái sang. Gọi ~l~ là vị trí của dấu ngoặc đơn trái "(" tương thích với dấu ngoặc ")" đó. Khi đó ~w_i~ chính bằng số lượng dấu ngoặc đơn phải ")" nằm trong đoạn từ ~l~ tới ~r~.

  • Ví dụ: Ta có chuỗi ~S=(((()()())))~. Khi đó ta có dãy ~P~ tương ứng là: ~P=4,5,6,6,6,6~ và dãy ~W~ tương ứng là ~W=1,1,1,4,5,6~. ~W[1] = 1~ vì dấu ngoặc đơn ")" thứ nhất nằm ở vị trí ~5~ tương ứng với dấu ngoặc "(" nằm ở vị trí ~4~. Trong đoạn ~4~ tới ~5~ của ~S~ có ~1~ dấu ngoặc đơn ")".

Yêu cầu: Cho dãy ~P~ bất kì, tìm dãy ~W~ tương ứng.

Input:

  • Dòng thứ nhất chứa chứa số nguyên dương ~n(1\le n\le 10^5)~ - Là độ dài của dãy ~P~

  • Dòng thứ hai chứa ~n~ số nguyên dương ~p_i(1\le p_i\le n)~ - Mỗi số cách nhau bởi dấu cách.

Output:

  • Nếu không tồn tại dãy ~W~ thỏa mãn yêu cầu bài toán, in ra "-1". Ngược lại, in ra dãy ~W~ cần tìm

Ví du:

Input:

3
2 2 3

Output:

1 2 1
  • Subtask 1: ~1\le n\le 10~. (10%)

  • Subtask 2: ~11 \le n \le 100~.(20%)

  • Subtask 3: ~101 \le n \le 5000~.(30%)

  • Subtask 4: ~5001 \le n \le 10^5~. (40%)


View comments (3)

Comments


  • 0
    Maowonh  commented on 10:47 p.m. 23 jul, 2020 edited

    trong bài này test 31, test 42, test 53, test 55, test 56 có phải chuỗi ngoặc đơn đúng ko ạ, vì code của em nếu ko phải dãy ngoặc đơn đúng sẽ âm chỉ số mảng nên bị runtime error


    • 2
      jumptozero  commented on 11:15 p.m. 23 jul, 2020

      Nếu không phải là dãy ngoặc đúng thì in ra -1 bạn !


      • 0
        Maowonh  commented on 11:25 p.m. 23 jul, 2020

        thanks, đọc ko kĩ đề