זוהי בעיה עם שתי הרצות. בכל בדיקה הפתרון שלכם יורץ פעמיים.
בשיעור מדעי המחשב, Алеся ו-Борис לומדים קריפטוגרפיה. הילדים החליטו להמציא שיטה משלהם להצפנת הודעות.
Алеся בוחרת $k$ מספרים שלמים שונים בין $1$ ל-$n$, ומסמנת את הקבוצה שהתקבלה ב-$T$. Алеся רוצה להעביר ל-Борис את הקבוצה $T$ כהודעה מוצפנת. לשם כך היא תבנה מתוך הקבוצה $T$ קבוצה אחרת, $R$, שגם היא מורכבת ממספרים שלמים בין $1$ ל-$n$, ותעביר אותה ל-Борис.
הילדים אינם רוצים שגודל ההודעה ישתנה לאחר ההצפנה, ולכן גם $R$ חייבת להכיל בדיוק $k$ מספרים. בנוסף, הם סבורים שאם ל-$T$ ול-$R$ יהיה אפילו איבר משותף אחד, ההצפנה שלהם לא תהיה אמינה מספיק. לכן אסור שיהיה מספר השייך גם ל-$T$ וגם ל-$R$, כלומר הקבוצות $T$ ו-$R$ חייבות להיות זרות. מובטח כי $k\le n/2$, ולכן תמיד אפשר לבנות מתוך הקבוצה $T$ לפחות קבוצה אחת $R$.
כאשר Борис יקבל את ההודעה המוצפנת $R$, עליו לפענח אותה ולשחזר את ההודעה המקורית $T$.
עזרו ל-Алеся ול-Борис להמציא ולממש אלגוריתמים להצפנה ולפענוח. בהרצה הראשונה התוכנית שלכם תפעל בתפקיד Алеся, ובהרצה השנייה — בתפקיד Борис.
קלט
בשורה הראשונה של הקלט נתון מספר אחד $a$, השווה ל-$1$ או ל-$2$ — מספר ההרצה של התוכנית שלכם.
בשורה השנייה נתון מספר אחד $m$ — מספר ההודעות ($1\le m\le300\,000$) שעל התוכנית שלכם להצפין (בהרצה הראשונה) או לפענח (בהרצה השנייה).
$2m$ השורות הבאות מכילות תיאורים של $m$ הודעות, שתי שורות לכל הודעה.
בשורה הראשונה של כל הודעה כתובים שני מספרים שלמים $n_i$ ו-$k_i$ ($2\le n_i\le10^9$, $1\le k_i\le300\,000$, $k_i\le\frac{n_i}{2}$). בשורה השנייה של ההודעה כתובים $k_i$ מספרים שלמים שונים בין $1$ ל-$n_i$, בסדר עולה.
מובטח שסכום כל ערכי $k_i$ בבדיקה אחת אינו עולה על $300\,000$.
אם $a=1$, המספרים הנתונים הם ההודעה המקורית. אם $a=2$, המספרים הנתונים הם תוצאת הרצת התוכנית שלכם להצפנת הודעה כלשהי בהרצה הראשונה של התוכנית.
פלט
על התוכנית להדפיס $m$ שורות. השורה ה-$i$ חייבת להכיל $k_i$ מספרים שלמים שונים בין $1$ ל-$n_i$, בסדר עולה.
בהרצה הראשונה, לכל הודעה מקורית $T_i$, על התוכנית להדפיס קבוצה $R_i$ שחייבת להיות זרה ל-$T_i$.
בהרצה השנייה, לכל הודעה מוצפנת $R_i$, על התוכנית לשחזר את ההודעה המקורית $T_i$.
דוגמאות
הרצה ראשונה
קלט 1
1 2 2 1 1 5 2 1 4
פלט 1
2 2 3
הרצה שנייה
קלט 2
2 2 5 2 2 3 2 1 2
פלט 2
1 4 1
הערה
שימו לב שבדוגמה מוצגות אפשרויות מסוימות לפלט בהרצה הראשונה ולקלט בהרצה השנייה. אם התוכנית שלכם תדפיס קבוצה אחרת $R$, גם הקלט בהרצה השנייה יהיה שונה.
בנוסף, בהרצה השנייה ההודעות המוצפנות אינן מועברות בהכרח לתוכנית המשתתף באותו סדר שבו הופיעו בהרצה הראשונה.
תתי-משימות
כדי לציין מגבלות נוספות על נתוני הקלט, נסמן את סדרת המספרים המגדירים את הקבוצה $T_i$ ב-$t_1,t_2,\ldots,t_{k_i}$. הם מסודרים בסדר עולה.
נסמן את סכום ערכי $n_i$ בבדיקה אחת ב-$N$.
נסמן את סכום ערכי $k_i$ בבדיקה אחת ב-$K$.
| תת-משימה | נקודות | מגבלות נוספות: $n_i,N$ | מגבלות נוספות: $k_i,K$ | מגבלות נוספות: $t_j$ | תתי-משימות נדרשות | מידע על הבדיקה |
|---|---|---|---|---|---|---|
| $1$ | $9$ | $N\le5000$ | $k_i=1$ | השגיאה הראשונה | ||
| $2$ | $11$ | $N\le5000$ | $k_i=2$ | השגיאה הראשונה | ||
| $3$ | $9$ | $N\le300\,000$ | $k_i=\frac{n_i}{2}$ | השגיאה הראשונה | ||
| $4$ | $7$ | $n_i\le7$, $N\le5000$ | דוגמאות | השגיאה הראשונה | ||
| $5$ | $9$ | $t_{j+1}-t_j\ge2$, $t_{k_i}\le n_i-1$ | השגיאה הראשונה | |||
| $6$ | $9$ | $t_{k_i}-t_1\le\frac{n_i}{2}-1$ | השגיאה הראשונה | |||
| $7$ | $10$ | $N \le 5000$ | $t_{k_i}\le n_i-k_i$ | השגיאה הראשונה | ||
| $8$ | $12$ | $N\le100$ | דוגמאות | השגיאה הראשונה | ||
| $9$ | $3$ | $N\le5000$ | דוגמאות, $1$–$2$, $4$, $7$–$8$ | השגיאה הראשונה | ||
| $10$ | $7$ | $N \le 300\,000$ | דוגמאות, $1$–$4$, $7$–$9$ | השגיאה הראשונה | ||
| $11$ | $7$ | $K\le5000$ | דוגמאות, $1$–$2$, $4$, $7$–$9$ | השגיאה הראשונה | ||
| $12$ | $7$ | ללא מגבלות נוספות | דוגמאות, $1$–$11$ | השגיאה הראשונה |