CSES - Two Stacks Sorting | Sắp xếp bằng Hai Ngăn xếp

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
Elektrikar
Dạng bài
Ngôn ngữ cho phép
Assembly, Awk, C, C#, C++, Clang, Clang++, Cobol, D, Groovy, Haskell, Java, JS, Kotlin, Lua, Node JS, ObjectiveC, OCaml, Output, Pascal, Perl, PHP, Prolog, Pypy, Pypy 3, Python, Ruby, Rust, Scala, Swift
Điểm: 2100 Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Bạn được cho một dãy input gồm \(n\) số. Mỗi số nguyên từ \(1\) đến \(n\) xuất hiện đúng một lần trong dãy.

Nhiệm vụ của bạn là tạo một dãy output đã sắp xếp sử dụng hai ngăn xếp (stack). Ở mỗi bước, bạn có thể thực hiện một trong các thao tác sau:

  • Di chuyển số đầu tiên từ dãy input vào một stack
  • Di chuyển một số từ một stack đến cuối dãy output

Input

Dòng đầu tiên là một số nguyên \(n\).

Dòng thứ hai chứa \(n\) số nguyên: các số của dãy input.

Output

In ra \(n\) số nguyên: với mỗi số là stack nó được chuyển vào (\(1\) hoặc \(2\)).

Bạn có thể in ra bất kỳ đáp án hợp lệ nào. Nếu không có đáp án, in ra IMPOSSIBLE.

Giới hạn

  • \(1 \le n \le 2 \cdot 10^5\)

Ví dụ

Input

5
2 3 1 5 4

Output

1 2 1 1 2

Bình luận


  • 1
    vanphukhang_0604    11:37 p.m. 23 Tháng 8, 2023 ← đã chỉnh sửa

    CSES - Two Stacks Sorting | Sắp xếp bằng hai ngăn xếp

    Bạn được cho một dãy input gồm \(n\) số. Mỗi số nguyên từ \(1, \ldots, n\) xuất hiện đúng một lần trong dãy.

    Nhiệm vụ của bạn là tạo một dãy output đã sắp xếp sử dụng hai ngăn xếp (stack). Ở mỗi bước, bạn có thể thực hiện một trong các thao tác sau:

    • Di chuyển số đầu tiên từ dãy input vào một stack
    • Di chuyển một số từ một stack đến cuối dãy output

    Input

    • Dòng đầu tiên chứa số nguyên \(n \ (1 \leq n \leq 2 \cdot 10^5)\).
    • Dòng thứ hai chứa \(n\) số nguyên: các số của dãy input.

    Output

    • In ra \(n\) số nguyên thể hiện stack mà mỗi số trong dãy input được đưa vào. Bạn có thể in bất kì cách sắp xếp nào hợp lệ.
    • Nếu không có cách sắp xếp, hãy in ra IMPOSSIBLE.

    Example

    Test 1

    Input 
    5
2 3 1 5 4
    Output 
    1 2 1 1 2