هذه مسألة تفاعلية.
على منضدة متجر الحلويات 跳蚤، يوجد صفان من الهلام الملوّن ذي الطبقتين (الطبقة العليا هي $a$، والسفلى هي $b$). وفقًا لقاعدة «التكامل عند التماسك» في المتجر، فإن مجموع ارتفاعي الطبقتين العليا والسفلى في كل مجموعة من الهلام يساوي بالضبط $n+1$. كان العاملون قد رتّبوا ارتفاعات كل من الصفين لتشكّل تبديلًا مثاليًا للأعداد من $1 \sim n$، لكن العامل المرح 跳蚤 قلب، دون قصد، الطبقتين العليا والسفلى في بعض المواضع ليلة أمس!
والآن، يوشك مهرجان الحلويات السنوي على الافتتاح، ويجب على العاملين استعادة الترتيب الأصلي للهلام قبل قلبه (أي تسلسل ارتفاعات الطبقة العليا $a$ قبل القلب).
لا يمكنك مشاهدة ارتفاعات الهلام مباشرة، لكن يمكنك إرسال تعليمات إلى جهاز القياس الآلي في المتجر: تحدّد بعض المواضع $i$، فيقلب الجهاز الطبقتين العليا والسفلى في هذه المواضع، ثم يعيد الفرق بين أكبر ارتفاع وأصغر ارتفاع (المدى) في الطبقة العليا الحالية، وكذلك الفرق بين أكبر ارتفاع وأصغر ارتفاع (المدى) في الطبقة السفلى. انتبه: يبقى أثر كل عملية قلب.
هل تستطيع استعادة تسلسل الطبقة العليا الأصلي بنجاح باستخدام عدد محدود من عمليات القلب والقياس؟
تختار المكتبة التفاعلية أولًا تبديلًا $p$ للأعداد من $1\sim n$، وتبني التبديل $b_i=n+1-p_i$. ثم تقرّر المكتبة، بصورة مستقلة لكل فهرس $i$، ما إذا كانت ستبدّل العددين في الموضع $i$. لنسمِّ المصفوفتين الناتجتين بعد هذه التبديلات $a,b$. عندئذٍ تتحقق دائمًا العلاقة $a_i+b_i=n+1$، لكن ليس من الضروري أن تبقى $a,b$ تبديلين.
تعرف $n$، لكنك لا تعرف هاتين المصفوفتين. يمكنك اختيار بعض المواضع وتبديل $a_i,b_i$ فيها؛ ستخبرك المكتبة التفاعلية بمدى كل من المصفوفتين بعد التبديل. يبقى أثر كل تبديل.
مهمتك هي استعادة المصفوفة $a$ قبل الاستعلام الأول. وتُعد الإجابة صحيحة أيضًا إذا أصبحت المصفوفة المعادة مطابقة للمصفوفة المطلوبة بعد استبدال كل قيمة $x$ فيها، في الوقت نفسه، بالقيمة $n+1-x$.
تفاصيل التنفيذ
لا يحتاج المتسابق إلى تنفيذ الدالة main، ولا ينبغي له تنفيذها.
يجب على المتسابق تضمين ملف الترويسة range.h في الملف المصدري recover.cpp، وتنفيذ الدالة التالية:
std::vector<int> recover(int c, int n);- يمثّل $c$ رقم المهمة الفرعية الحالية، ويأخذ القيم $1,2,3,4$ في الاختبارات الرسمية، والقيمة $0$ في المثال. ويمثّل $n$ طول المصفوفة. تستدعي المكتبة التفاعلية
recoverمرة واحدة بالضبط لكل حالة اختبار. - يجب أن تكون القيمة المعادة مصفوفة أعداد صحيحة بطول $n$، تمثّل $a$ قبل الاستعلام الأول، أو متممتها بالكامل.
يمكن للمتسابق استدعاء الدالة التالية:
std::pair<int, int> query(const std::vector<int>& positions);- يجب أن تكون الفهارس في
positionsمختلفة اثنين اثنين، وأن تنتمي إلى $[0,n-1]$. يُسمح بتمرير مصفوفة فارغة. - تبدّل المكتبة التفاعلية القيمتين الحاليتين $a_i,b_i$ مرة واحدة لكل فهرس في
positions، ثم تعيد مدى $a$ الحالية ومدى $b$ الحالية. تتراكم التبديلات بين الاستعلامات، لكن عند إعادة الإجابة يجب استعادة المصفوفة الأولية قبل التبديلات. - يُعرَّف المدى بأنه أكبر قيمة في المصفوفة ناقص أصغر قيمة فيها. وبما أن العلاقة $b_i=n+1-a_i$ تتحقق دائمًا، فإن المديين متساويان بالضرورة.
- يجب ألا يتجاوز عدد استدعاءات
queryالحد الأعلى $Q_{\max}$ لحالة الاختبار الحالية.
المكتبة التفاعلية غير تكيفية: تُحدَّد المصفوفة الأولية قبل بدء recover، ولا تتغيّر تبعًا لاستعلامات المتسابق. قد تختلف المكتبة المستخدمة في التقييم النهائي عن مكتبة المثال الموزّعة؛ ويُمنع برنامج المتسابق من قراءة البيانات الداخلية للمكتبة التفاعلية أو التعامل مباشرة مع تدفّقي الإدخال والإخراج القياسيين.
طريقة اختبار البرنامج
ضع recover.cpp وrange.h وملف grader.cpp الموجود في المرفقات في المجلد نفسه، ثم ترجم باستخدام C++17:
g++ grader.cpp recover.cpp -o recover -O2 -std=c++17
./recover < ex_range1.inالسطر الأول الذي تقرؤه المكتبة التفاعلية المحلية هو $c,n,Q_{\max}$؛ والسطر الثاني هو التبديل $p_0,\ldots,p_{n-1}$؛ والسطر الثالث يحتوي على $n$ أعداد من نوع $0/1$، حيث يشير $1$ إلى تبديل ذلك الموضع قبل بدء التفاعل. لا يُعطى المتسابق عبر معاملات الدالة إلا $c,n$؛ ولا يُمرَّر التبديل أو علامات التبديل أو الحد الأعلى لعدد الاستعلامات مباشرة إلى برنامج المتسابق.
إذا كانت الإجابة صحيحة، تطبع المكتبة التفاعلية المحلية Correct! في السطر الأول، وQueries used: Q في السطر الثاني، حيث $Q$ هو عدد الاستعلامات المستخدمة في هذا الاستدعاء. وإذا كانت الإجابة خاطئة، تطبع Wrong answer.؛ وإذا كان استدعاء الواجهة غير صالح، فإنها تبيّن سبب الخطأ أيضًا في تدفّق الأخطاء القياسي.
أمثلة
الإدخال 1
0 6 67
3 1 6 4 2 5
0 1 1 0 1 0الإخراج 1
Correct!
Queries used: 16ملاحظة
في المثال، تكون المصفوفة قبل بدء التفاعل $a=(3,6,1,4,5,5)$؛ ومتممتها بالكامل هي $(4,1,6,3,2,2)$. تُعد إعادة أي منهما صحيحة. يعيد الاستدعاء الأول query({}) الزوج $(5,5)$. يتوافق الإخراج أعلاه مع نتيجة تشغيل البرنامج النموذجي الموجود في المرفقات؛ وقد تختلف أعداد الاستعلامات بين البرامج الصحيحة المختلفة.
القيود
في جميع بيانات الاختبار، $1\le n\le 500$.
| المهمة الفرعية | النقاط | $n \le$ | $Q_{\max} = $ | خصائص خاصة |
|---|---|---|---|---|
| $1$ | $10$ | $20$ | $50000$ | لا توجد |
| $2$ | $10$ | $100$ | $21000$ | لا توجد |
| $3$ | $40$ | $500$ | $50000$ | يُضمن أن $a$ الأولية تبديل للأعداد من $1 \sim n$ |
| $4$ | $40$ | $500$ | $50000$ | لا توجد |
تُحسب نقاط كل مهمة فرعية وفقًا لحالة الاختبار التي لها أصغر معامل نقاط فيها، كما هو موضّح أدناه.
المهام الفرعية
إذا كانت الإجابة التي تعيدها recover غير صحيحة، أو كانت معاملات query غير صالحة، أو تجاوز عدد الاستعلامات $Q_{\max}$، فإن نقاط حالة الاختبار هذه تساوي $0$.
وإلا، تحصل حالة الاختبار على كامل النقاط في المهمتين الفرعيتين $1,2$. أما في المهمتين الفرعيتين $3,4$، فليكن $Q$ عدد الاستعلامات المستخدمة فعليًا في حالة الاختبار؛ يُحسب معامل النقاط $f(Q)$ وفقًا للجدول التالي:
| نطاق $Q$ | $f(Q)$ |
|---|---|
| $Q\le5000$ | $1$ |
| $5000 < Q\le10000$ | $1-\dfrac{Q-5000}{20000}$ |
| $10000 < Q\le20000$ | $\dfrac34-\dfrac{Q-10000}{40000}$ |
| $20000 < Q\le50000$ | $\dfrac12-\dfrac{Q-20000}{100000}$ |
| $Q>50000$ | $0$ |
| $Q$ | لا يتجاوز $5000$ | $10000$ | $20000$ | $50000$ | يتجاوز $50000$ |
|---|---|---|---|---|---|
| $f(Q)$ | $100\%$ | $75\%$ | $50\%$ | $20\%$ | $0\%$ |
نقاط المهمة الفرعية $3$ هي $40f(Q)$، ونقاط المهمة الفرعية $4$ هي $40f(Q)$. تُقرَّب النقاط النهائية إلى $3$ منازل بعد الفاصلة العشرية.
الحد الزمني: $2\ \mathrm{s}$.
حد الذاكرة: $512\ \mathrm{MiB}$.