CSES - Two Stacks Sorting | Sắp xếp bằng Hai Ngăn xếp
Xem PDF
Đ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
Bạn được cho một dãy input gồm
n
n số. Mỗi số nguyên từ
1
1 đến
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
n.
Dòng thứ hai chứa
n
n số nguyên: các số của dãy input.
Output
In ra
n
n số nguyên: với mỗi số là stack nó được chuyển vào (
1
1 hoặc
2
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
≤
n
≤
2
⋅
1
0
5
1≤n≤2⋅10
5
Ví dụ
Input
Copy
5
2 3 1 5 4
Output
Copy
1 2 1 1 2
-3
Thích
Bình luận
(2)
Lưu
Chia sẻ
Báo cáo
Bình luận
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
n số. Mỗi số nguyên từ
1
,
…
,
n
1,…,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
≤
n
≤
2
⋅
1
0
5
)
n (1≤n≤2⋅10
5
).
Dòng thứ hai chứa
n
n số nguyên: các số của dãy input.
Output
In ra
n
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
-2
Phản hồi
Chia sẻ
Elektrikar
•
2:09 p.m. 8 Tháng 9, 2023
•
OK...
4
Phản hồi
Chia sẻ
Bài tập gợi ý:
CSES - School Dance | Vũ hội trường
CSES - Another Game | Trò chơi với đồng xu
CSES - Counting Bishops | Đếm số quân tượng
CSES - Writing Numbers | Viết số
CSES - Coding Company | Công ty coding
CSES - Knight's Tour | Hành trình của quân mã
CSES - Distinct Substrings | Xâu con phân biệt
CSES - String Reorder | Đảo xâu
1 bình luận nữa