Universal Cup Judging System

Universal Cup

حد الوقت: 1 s حد الذاكرة: 64 MB
الإحصائيات

給定三個長度為 $n$ 的排列 $a$、$b$ 與 $c$。將排列 $c$ 作用於陣列 $a$ 會產生一個滿足對所有 $i$ 都有 $d[c[i]] = a[i]$ 的陣列 $d$。

在將 $c$ 作用於 $a$ 之前,你可以對排列 $c$ 進行任意次數的操作。在一次操作中,你可以選擇兩個索引 $i$ 與 $j$,並交換 $c[i]$ 與 $c[j]$。

對於從 $0$ 到 $n$ 的每個 $k$,求出最少需要進行多少次操作,使得將修改後的排列 $c$ 作用於 $a$ 所產生的陣列與 $b$ 恰好在 $k$ 個位置上不同,或者判定這是不可能的。

輸入格式

第一行包含一個整數 $t$($1 \le t \le 5 \cdot 10^4$),代表測試資料的組數。

每組測試資料的第一行包含一個整數 $n$($1 \le n \le 10^6$)。

接下來的三行分別包含長度為 $n$ 的排列 $a$、$b$ 與 $c$。每個排列都恰好包含從 $1$ 到 $n$ 的每個整數各一次。

所有測試資料中 $n$ 的總和皆不超過 $10^6$。

輸出格式

對於每組測試資料,輸出 $n + 1$ 個整數,其中第 $k$ 個整數代表為了恰好得到 $k$ 處不同所需的最少操作次數;若不可能,則輸出 $-1$。

範例

輸入格式 1

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

輸出格式 1

0 -1 1 2
1 -1 0

說明

在第一組測試資料中,陣列為 $a = [1, 2, 3]$。在套用排列 $c = [2, 3, 1]$ 之後,來自第 $1$ 個位置的元素移動到第 $2$ 個位置,第 $2$ 個位置的元素移動到第 $3$ 個位置,第 $3$ 個位置的元素移動到第 $1$ 個位置,最終得到的陣列為 $d = [3, 1, 2]$。在這種情況下,它與陣列 $b$ 完全一致。因此,$k = 0$ 處不同對應的答案為 $0$ 次操作。

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.