trang chủ / bài tập / permrec

Khôi phục hoán vị

Vasya viết ra một hoán vị $p_{1}, p_{2}, \dots, p_{n}$ của các số nguyên từ $1$ đến $n$ , nghĩa là $1 \leq p_{i} \leq n$ với mọi $i$ và tất cả $p_{i}$ đôi một khác nhau.

Sau đó, với mỗi vị trí $i$ bạn ấy ghi thêm một số $n e x t_{i}$ , được định nghĩa là chỉ số $j$ nhỏ nhất thoả mãn $i < j \leq n$ và $p_{j} > p_{i}$ . Nếu không tồn tại $j$ như vậy thì $n e x t_{i} = n + 1$ .

Trên đường về nhà trời mưa làm ướt quyển vở. Toàn bộ hoán vị và một vài giá trị $n e x t_{i}$ đã không còn đọc được nữa. Những giá trị $n e x t_{i}$ bị mất được ghi lại là $- 1$ .

Cho dãy $n e x t_{1}, n e x t_{2}, \dots, n e x t_{n}$ , hãy khôi phục một hoán vị $p$ bất kỳ sao cho mọi giá trị $n e x t_{i}$ khác $- 1$ đều đúng theo định nghĩa trên. Các vị trí có $n e x t_{i} = - 1$ không đặt ra ràng buộc nào.

Dữ liệu vào

Dòng đầu chứa số nguyên $t$ : số lượng bộ dữ liệu.
Tiếp theo là 2t dòng mô tả các bộ dữ liệu, mỗi bộ gồm hai dòng:
- Dòng thứ nhất chứa số nguyên $n$ : độ dài hoán vị.
- Dòng thứ hai chứa $n$ số nguyên $n e x t_{1}, n e x t_{2}, \dots, n e x t_{n}$ .

Dữ liệu ra

In ra $t$ dòng, dòng thứ $i$ là đáp án cho bộ dữ liệu thứ $i$ .

Nếu không tồn tại hoán vị nào thoả mãn, in ra $- 1$ . Ngược lại, in ra $n$ số nguyên đôi một khác nhau $p_{1}, p_{2}, \dots, p_{n}$ . Nếu có nhiều đáp án, in ra một đáp án bất kỳ.

Ràng buộc

$1 \leq t \leq 100 000$
$1 \leq n \leq 500 000$
$n e x t_{i} = - 1$ hoặc $i < n e x t_{i} \leq n + 1$
Tổng $n$ trên tất cả các bộ dữ liệu không vượt quá $500 000$

Ví dụ

Input	Output	Giải thích
3 3 2 3 4 2 3 3 3 -1 -1 -1	1 2 3 2 1 1 2 3	Bộ 1: với $p = [1, 2, 3]$ thì mỗi phần tử đều nhỏ hơn phần tử kế tiếp nên $n e x t = [2, 3, 4]$ . Đây cũng là hoán vị duy nhất thoả mãn. Bộ 2: $n e x t_{1} = 3 = n + 1$ buộc $p_{2} < p_{1}$ , nên $p = [2, 1]$ . Bộ 3: mọi giá trị đều bị mất nên hoán vị nào cũng hợp lệ.
3 3 3 4 -1 1 2 4 4 -1 4 5	-1 1 3 1 2 4	Bộ 1: $n e x t_{1} = 3$ buộc $p_{2} < p_{1} < p_{3}$ , còn $n e x t_{2} = 4 = n + 1$ buộc $p_{3} < p_{2}$ . Hai điều này mâu thuẫn nên đáp án là $- 1$ . Bộ 2: chỉ có một hoán vị độ dài $1$ . Bộ 3: $n e x t_{1} = 4$ buộc $p_{2}, p_{3} < p_{1} < p_{4}$ , còn $n e x t_{3} = 4$ buộc $p_{3} < p_{4}$ . Hoán vị $[3, 2, 1, 4]$ cũng được chấp nhận.

Bình luận

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

Nộp bài giải

Danh sách bài nộp Bài nộp tốt nhất

Điểm 7,00một phần

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

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

Đầu vào stdin

Kết quả của bạn stdout

Dạng bài

Chưa phân loại

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, F#, Forth, Fortran, Go, Groovy, Java, Javascript, Julia, Kotlin, Lean, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, Swift, TCL, Typescript, V, Visual Basic, Zig

Đề bài

Mô tả

Dữ liệu vào

Dữ liệu ra

Ràng buộc

Ví dụ

Bình luận