Universal Cup Judging System

Universal Cup

Süre Sınırı: 1 s Bellek Sınırı: 64 MB
İstatistikler

Bạn được cho ba hoán vị $a$, $b$ và $c$ có độ dài $n$. Việc áp dụng hoán vị $c$ lên mảng $a$ sẽ tạo ra một mảng $d$ sao cho $d[c[i]] = a[i]$ với mọi $i$.

Trước khi áp dụng $c$ lên $a$, bạn có thể thực hiện một thao tác trên hoán vị $c$ với số lần tùy ý. Trong một thao tác, bạn có thể chọn hai chỉ số $i$ và $j$ rồi hoán đổi $c[i]$ và $c[j]$.

Với mỗi $k$ từ $0$ đến $n$, hãy tìm số thao tác tối thiểu để sau đó việc áp dụng hoán vị $c$ đã sửa đổi lên $a$ tạo ra một mảng khác với $b$ ở đúng $k$ vị trí, hoặc xác định rằng điều đó là không thể.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $t$ ($1 \le t \le 5 \cdot 10^4$), là số lượng bộ dữ liệu.

Dòng đầu tiên của mỗi bộ dữ liệu chứa một số nguyên $n$ ($1 \le n \le 10^6$).

Ba dòng tiếp theo chứa các hoán vị $a$, $b$ và $c$ có độ dài $n$. Mỗi hoán vị chứa mọi số nguyên từ $1$ đến $n$ đúng một lần.

Tổng của $n$ trên tất cả các bộ dữ liệu không vượt quá $10^6$.

Dữ liệu ra

Với mỗi bộ dữ liệu, hãy in ra $n + 1$ số nguyên, trong đó số thứ $k$ là số thao tác tối thiểu cần thiết để thu được đúng $k$ vị trí khác nhau, hoặc $-1$ nếu điều đó là không thể.

Ví dụ

Dữ liệu vào 1

2
3
1 2 3
3 1 2
2 3 1
2
2 1
1 2
1 2

Dữ liệu ra 1

0 -1 1 2
1 -1 0

Ghi chú

Ở bộ dữ liệu đầu tiên, mảng là $a = [1, 2, 3]$. Sau khi áp dụng hoán vị $c = [2, 3, 1]$, phần tử từ vị trí thứ $1$ chuyển sang vị trí thứ $2$, từ vị trí thứ $2$ sang vị trí thứ $3$, và từ vị trí thứ $3$ sang vị trí thứ $1$, nên mảng thu được là $d = [3, 1, 2]$. Trong trường hợp này, nó trùng khớp với mảng $b$. Vì vậy, đáp án cho $k = 0$ vị trí khác nhau là $0$ thao tác.

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.