Hoán Vị Yêu Thích Của FJ

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Farmer John có một hoán vị $p$ độ dài $N$ ( $2 \leq N \leq 10^{5}$ ). Farmer Nhoj đã tháo rời hoán vị và tạo ra gợi ý bằng quy trình sau:

Gọi $p_{1}^{'}, p_{2}^{'}, \dots, p_{m}^{'}$ là các phần tử còn lại (ban đầu $m = N$ ). Lặp lại cho đến khi còn 1 phần tử:

Nếu $p_{1}^{'} > p_{m}^{'}$ : ghi ra $p_{2}^{'}$ và xóa $p_{1}^{'}$
Ngược lại ( $p_{1}^{'} \leq p_{m}^{'}$ ): ghi ra $p_{m - 1}^{'}$ và xóa $p_{m}^{'}$

Quy trình tạo ra $N - 1$ giá trị gợi ý $h_{1}, h_{2}, \dots, h_{N - 1}$ .

Cho dãy $h$ , tìm hoán vị $p$ nhỏ nhất theo thứ tự từ điển thỏa mãn gợi ý, hoặc in $- 1$ nếu không tồn tại.

Dòng 1: Số nguyên $T$ -- số test case ( $1 \leq T \leq 10$ )
Mỗi test case:
- Dòng 1: Số nguy��n $N$
- Dòng 2: $N - 1$ số nguyên $h_{1}, h_{2}, \dots, h_{N - 1}$ ( $1 \leq h_{i} \leq N$ )

Với mỗi test case, in hoán vị nhỏ nhất theo thứ tự từ điển, hoặc $- 1$ nếu không khả thi.

Input	Output	Giải thích
5 2 1 2 2 4 1 1 1 4 2 1 1 4 3 2 1	1 2 -1 -1 3 1 2 4 1 2 3 4	Test 1: $p = [1, 2]$ , $p_{1}^{'} = 1 \leq p_{2}^{'} = 2$ , ghi $p_{1}^{'} = 1$ . Test 4: $p = [3, 1, 2, 4]$ , bước 1: $3 \leq 4$ nên ghi $p_{3}^{'} = 2$ ; bước 2: $[3, 1, 2]$ , $3 > 2$ nên ghi $p_{2}^{'} = 1$ ; bư��c 3: $[1, 2]$ , $1 \leq 2$ nên ghi $1$ .

Bình luận

Không có bình luận tại thời điểm này.