P151PROG spoj PTIT – Xếp Hàng

Nguồn đề bài: http://www.spoj.com/PTIT/problems/P151PROG/

1. Đề bài P151PROG spoj PTIT

Trong giờ ăn trưa tại Học viên Công nghệ Bưu chính Viễn thông, có n sinh viên đang xếp hang để lấy đồ.

Cảm thấy chán vì phải đứng đợi một mình, vì vậy mỗi sinh viên viết ra mã sinh viên của mình đứng ngay trước và ngay sau của mình. Nếu không có ai đứng trước hoặc không có ai đứng sau thì viết ra 0.

Đột nhiên, xe chở nước sôi đi qua, tất cả sinh viên phải tránh. Khi họ trở lại, họ không nhớ vị trí của mình mà chỉ nhớ mã sinh viên của người đừn trước và người đứng sau.

Hãy giúp các sinh viên PTIT tìm lại vị trí của mình!!!!

Input

Dòng đầu tiên gồm số tự nhiên n (2 ≤ n ≤ 2·10^5) – số lượng sinh viên.

n dòng tiếp theo, dòng thứ i gồm cặp số tự nhiên ai, bi (0 ≤ ai, bi ≤ 10^6), với ai là mã sinh viên của người đứng trước, bi là mã sinh viên của người đứng sau 1 sinh viên nào đó. Nếu không có ai đứng trước hoặc không có ai đứng sau nhập 0.

Mã sinh viên của mỗi sinh viên là khác nhau.

Output

Trên 1 dòng, in ra n số  x1, x2, …, xn  , danh sách của các sinh viên theo thứ tự ban đầu.

Example

Input:
4
92 31
0 7
31 0
7 141
Output:
92 7 31 141

2. Hướng dẫn P151PROG spoj PTIT

Nhận Xét:

– Đề bài cho ta biết “Nếu không có ai đứng trước nhập 0” vậy có nghĩa ta sẽ xác định được kết quả ở vị trí thứ 2. tạm gọi số này là “số đầu tiên” đi.

Hướng dẫn:

– Từ nhận xét trên ta có thể tính được các vị trí 2, 4, 6, 8, ….. n

– Từ số đầu tiên, ta thực hiện chặt nhị phân tìm số trong dãy A[i] ( lưu ý là phải sort A, và B theo A truoc), gọi k là vị trí tìm thấy. rồi ghi kq vào vị trí 4, rồi tiếp tục lấy B[k] làm mốc xong rồi chặt rồi ghi vào vị trí 6, tương tự….8,…10,…n.. dừng lại khi k=0.

– Tương tự từ gợi ý trên bạn có thể dễ dàng tìm kết quả cho các vị trí 1, 3, 5, …..

* Thật ra lúc làm bài này mình quên việc có thể dùng mảng đánh dấu. nên các ban có thể dùng mảng đánh dấu. mà ko cần SORT và chặt nhị phân. code tham khảo mình viết theo ý tưởng chặt nhị phân. các bạn có thể code lại bằng đánh dấu sẽ dễ hơn…

####

Gợi ý của bạn Trình Gia Lạc:

có 2 thằng suất hiện 1 lần trong đó thằng nào ở bên trái thì là đầu tiên, thằng thứ 2 là thằng đứng R trong cặp (0, R), từ 2 thằng này suy luận ra tắt cả thằng còn lại: 1->3, 2 -> 4 ,…”

Lời giải từ BTC

Phân dãy sinh viên thành 2 dãy, một dãy là các sinh viên đứng ở vị trí chẵn, một dãy là các sinh viên đứng ở vị trí lẻ, sau đó gộp dãy.

Có thể xây dựng dãy các sinh viên ở vị trí lẻ bằng cách “nhảy” từ người có a = 0.

Dãy các sinh viên ở vị trí chẵn có thể xây dựng bằng phương pháp tương tự.

3. Code Tham khảo P151PROG spoj PTIT

4 thoughts on “P151PROG spoj PTIT – Xếp Hàng

Trả lời

Thư điện tử của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *