Universal Cup Judging System

Universal Cup

Time Limit: 1 s Memory Limit: 64 MB
Statistics

נתונות לך שלוש תמורות $a$, $b$ ו-$c$ באורך $n$. הפעלת התמורה $c$ על המערך $a$ יוצרת מערך $d$ כך שמתקיים $d[c[i]] = a[i]$ לכל $i$.

לפני הפעלת $c$ על $a$, ניתן לבצע פעולה על התמורה $c$ מספר כלשהו של פעמים. בפעולה אחת, ניתן לבחור שני אינדקסים $i$ ו-$j$ ולהחליף בין $c[i]$ לבין $c[j]$.

עבור כל $k$ מ-$0$ עד $n$, מצא את המספר המינימלי של פעולות שלאחריהן הפעלת התמורה המעודכנת $c$ על $a$ יוצרת מערך השונה מ-$b$ ב-$k$ מיקומים בדיוק, או קבע שזה בלתי אפשרי.

קלט

השורה הראשונה מכילה מספר שלם $t$ ($1 \le t \le 5 \cdot 10^4$), מספר מקרי הבדיקה.

השורה הראשונה של כל מקרה בדיקה מכילה מספר שלם $n$ ($1 \le n \le 10^6$).

שלוש השורות הבאות מכילות את התמורות $a$, $b$ ו-$c$ באורך $n$. כל תמורה מכילה כל מספר שלם מ-$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.