זוהי בעיה אינטראקטיבית.

ערב פתיחת פסטיבל הקינוחים, השף מעצב בקפידה את יצירת הדגל של החנות — „千层幻彩慕斯”. הקינוח מורכב מ־$n$ חתיכות מוס בטעמים שונים, הממוספרות לפי הסדר $0,1,\dots,n-1$.

אולם בתוך ההמולה, העוזר שיבש בטעות את סדר הצבת חתיכות המוס. כעת הן מסודרות בשורה משמאל לימין, ויוצרות תמורה לא ידועה של מיקומים $p=(p_0,p_1,\dots,p_{n-1})$, כאשר $p_i$ מציין את מספר חתיכת המוס המונחת במיקום ה־$i$.

כדי לברר את מיקומה המדויק של כל חתיכת מוס, תוכלו להיעזר במכשיר לבדיקת קינוחים. בכל בדיקה בוחרים שלושה מיקומים שונים זה מזה $x,y,z$, והמכשיר מחזיר את סכום המספר הקטן ביותר והמספר הגדול ביותר מבין שלוש חתיכות המוס האלה:

$$ \min(p_x,p_y,p_z)+\max(p_x,p_y,p_z). $$

פעמוני הפתיחה עומדים לצלצל. האם תוכלו לשחזר במדויק את מיקומה האמיתי של כל חתיכת מוס באמצעות מספר מוגבל של בדיקות?

נתונה תמורה $p$ באורך $n$, שאיבריה הם בדיוק $0,1,\ldots,n-1$. אינכם יודעים מהם איברי $p$ ובאיזה סדר הם מופיעים.

תוכלו לבחור שלושה אינדקסים שונים זה מזה $x,y,z$, והספרייה האינטראקטיבית תחזיר

$$ \min(p_x,p_y,p_z)+\max(p_x,p_y,p_z). $$

משימתכם היא לשחזר את התמורה כולה. מספר השאילתות המרבי ואופן חישוב הניקוד לפי מספר השאילתות מפורטים בהמשך.

פרטי מימוש

אין צורך לממש את הפונקציה main, ואין לממש אותה. קובץ קוד המקור המוגש צריך לכלול:

#include "mousse.h"

עליכם לממש את שתי הפונקציות הבאות:

void init(int c);
std::vector<int> mousse(int c, int n);

• $c$ הוא מספר תת־המשימה; $c=0$ מציין את הדוגמה. כל מקרה בדיקה מכיל מופע אחד בדיוק. עבור אותו מקרה בדיקה, הספרייה האינטראקטיבית קוראת פעם אחת ל־init(c), ולאחר מכן פעם אחת ל־mousse(c,n).
• על mousse להחזיר מערך באורך $n$, שבו האיבר ה־$i$ הוא $p_i$, והאינדקסים מתחילים ב־$0$.

תוכלו לקרוא לפונקציה הבאה כדי לבצע שאילתה אחת:

int query(int x, int y, int z);

חייב להתקיים $0\le x,y,z < n$, ועל $x,y,z$ להיות שונים זה מזה בזוגות. הפונקציה מחזירה $\min(p_x,p_y,p_z)+\max(p_x,p_y,p_z)$.

בדיקת התוכנית

הקבצים המצורפים כוללים את mousse.h, את הספרייה האינטראקטיבית המקומית grader.cpp ואת התוכנית לדוגמה template_mousse.cpp. שמרו את תוכניתכם בשם mousse.cpp; תוכלו להריץ את הפקודות הבאות מתוך תיקיית הבעיה:

g++ grader.cpp mousse.cpp -o mousse -O2 -std=c++14
./mousse < mousse1.in

הספרייה האינטראקטיבית המקומית קוראת את התמורה הנסתרת מהקלט הסטנדרטי. אסור לתוכניתכם לקרוא את הנתונים האלה בעצמה. פורמט הקלט הוא:

• השורה הראשונה מכילה שני מספרים שלמים $c,n$.
• השורה השנייה מכילה את $p_0,p_1,\ldots,p_{n-1}$.

אם התשובה נכונה, הספרייה האינטראקטיבית מדפיסה Correct! ו־Max queries used: Q, כאשר $Q$ הוא מספר השאילתות באותו מקרה בדיקה; אם התשובה שגויה, היא מדפיסה Wrong answer.. אם נמסרת שאילתה לא חוקית או נחצה מספר השאילתות המרבי, התוכנית מדפיסה הודעת שגיאה לערוץ השגיאות הסטנדרטי ומסיימת את פעולתה. ניתן להוסיף את הארגומנט -v כדי לראות את מספר השאילתות באותו מקרה בדיקה.

דוגמאות

קלט 1

0 10
0 2 9 1 5 8 3 7 6 4

פלט 1

Correct!
Max queries used: 15

הערה

לדוגמה, בקריאה ל־query(0,1,2), שלושת הערכים המתאימים הם $0,2,9$, והערך המוחזר הוא $0+9=9$. תוכנית הייחוס משתמשת ב־$15$ שאילתות עבור הנתונים האלה. אם תשתמשו באסטרטגיה אחרת, מספר זה עשוי להיות שונה.

מגבלות

בכל נתוני הבדיקה, $n\in\{10,100,10^5\}$, ו־$p$ היא תמורה של $0\sim n-1$. כל מקרה בדיקה מכיל מופע אחד בדיוק.

בדוגמה, $c=0$ ו־$n=10$, ומספר השאילתות המרבי הוא $1000$.

ניקוד

שימו לב:

• הספרייה האינטראקטיבית אינה אדפטיבית. התמורה של כל מקרה בדיקה נקבעת לפני הקריאה לתוכניתכם, ואינה משתנה בעקבות השאילתות.
• אסור להשיג את התמורה הנסתרת באמצעות קריאה מהקלט הסטנדרטי או בכל דרך אסורה אחרת. המימוש של הספרייה האינטראקטיבית המשמשת בבדיקה הסופית עשוי להיות שונה מזה של הספרייה המקומית.

אם במקרה בדיקה כלשהו mousse מחזירה תשובה שגויה, הארגומנטים של query אינם חוקיים, או שמספר השאילתות עולה על $Q_{\max}$ של תת־המשימה, מכפיל הניקוד של אותו מקרה בדיקה הוא $0$.

בתת־המשימות $1,2$, תקבלו את מלוא הניקוד של תת־המשימה רק אם כל מקרי הבדיקה נכונים.

בתת־המשימות $3,4$, אם מכפיל הניקוד של מקרה בדיקה כלשהו הוא $0$, הניקוד של תת־המשימה הוא $0$. אחרת, נסמן ב־$Q$ את מספר השאילתות הגדול ביותר מבין כל מקרי הבדיקה בתת־המשימה. מכפיל הניקוד $f(Q)$ נקבע לפי הטבלה הבאה:

אם $Q\le 99970$, אז $f(Q)=100\%$. אם $Q$ נמצא בין שתי שורות סמוכות בטבלה, $(Q_i,f_i)$ ו־$(Q_{i+1},f_{i+1})$, אז:

$$ f(Q)=f_i+\frac{Q-Q_i}{Q_{i+1}-Q_i}(f_{i+1}-f_i). $$

הניקוד של תת־המשימה $3$ הוא $30f(Q)$, והניקוד של תת־המשימה $4$ הוא $60f(Q)$. הניקוד הסופי מעוגל ל־$3$ ספרות אחרי הנקודה העשרונית.

מגבלת זמן: $10\ \mathrm{s}$.

מגבלת זיכרון: $512\ \mathrm{MiB}$.