هذه مسألة تفاعلية.
عشية افتتاح مهرجان الحلويات، يعكف رئيس الطهاة على إتقان تحفة المتجر الشهيرة، «千层幻彩慕斯». تتكون هذه الحلوى من $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$. تحتوي كل حالة اختبار على مجموعة بيانات واحدة بالضبط.
| رقم المهمة الفرعية | الدرجة | $n =$ | $Q_{\max} = $ | خاصية إضافية |
|---|---|---|---|---|
| $1$ | $5$ | $10$ | $1000$ | لا توجد |
| $2$ | $5$ | $100$ | $10000$ | لا توجد |
| $3$ | $30$ | $10^5$ | $2\times10^6$ | $p_0=0$ |
| $4$ | $60$ | $10^5$ | $2\times10^6$ | لا توجد |
في المثال، $c=0$ و$n=10$، والحد الأقصى لعدد الاستعلامات هو $1000$.
المهام الفرعية
انتبه:
- المكتبة التفاعلية غير تكيفية. يُحدد التبديل في كل حالة اختبار قبل استدعاء برنامج المتسابق، ولا يتغير استجابةً للاستعلامات.
- لا يجوز للمتسابق الحصول على التبديل المخفي بقراءة الإدخال القياسي أو بأي وسيلة غير مشروعة أخرى. قد يختلف تنفيذ المكتبة التفاعلية المستخدمة في التقييم النهائي عن تنفيذ المكتبة التفاعلية المحلية.
إذا أعادت mousse إجابة خاطئة في حالة اختبار، أو كانت معاملات query غير صالحة، أو تجاوز عدد الاستعلامات $Q_{\max}$ الخاص بالمهمة الفرعية، يكون معامل الدرجة لهذه الحالة $0$.
في المهمتين الفرعيتين $1,2$، لا تُمنح الدرجة الكاملة للمهمة الفرعية إلا إذا كانت جميع حالات الاختبار صحيحة.
في المهمتين الفرعيتين $3,4$، إذا كان معامل الدرجة لأي حالة اختبار $0$، تحصل المهمة الفرعية على $0$ نقطة. وإلا، ليكن $Q$ أكبر عدد من الاستعلامات بين جميع حالات الاختبار في هذه المهمة الفرعية؛ ويُحدد معامل الدرجة $f(Q)$ وفق الجدول التالي:
| عدد الاستعلامات $Q_i$ | معامل الدرجة $f_i$ |
|---|---|
| $99970$ | $100\%$ |
| $99975$ | $98\%$ |
| $99981$ | $95\%$ |
| $99988$ | $90\%$ |
| $99996$ | $84\%$ |
| $100000$ | $80\%$ |
| $100010$ | $74\%$ |
| $100026$ | $66\%$ |
| $100051$ | $58\%$ |
| $100093$ | $52\%$ |
| $150000$ | $32\%$ |
| $200000$ | $20\%$ |
| $1660964$ | $8\%$ |
| $2000000$ | $5\%$ |
إذا كان $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}$.