لمجموعة متعددة العناصر $S=\{x_0,x_1,\ldots,x_{m-1}\}$ حجمها $m$، لتكن نتيجة ترتيب جميع عناصرها تنازليًا $y_0\geq y_1\geq\cdots\geq y_{m-1}$. نعرّف وسيطها $\mathrm{Median}(S)$ بأنه العنصر الأكبر ذي الرتبة $\lceil m/2\rceil$، أي $\mathrm{Median}(S)=y_{\lceil m/2\rceil-1}$. انتبه: قد يختلف تعريف الوسيط في هذه المسألة عن التعريف المعتاد.

أُعطيت سلسلة $[a_0,a_1,\ldots,a_{n-1}]$ طولها $n$، وعدد صحيح موجب $k$، حيث $k\leq n$. نعرّف تقسيمًا كما يلي: اختر سلسلة متزايدة من الفهارس طولها $k-1$، تحقق $0<b_1<\cdots<b_{k-1}<n$، فتقسم السلسلة الأصلية إلى $k$ مقطعًا، ومجالات فهارسها على التوالي $[0,b_1),[b_1,b_2),\ldots,[b_{k-1},n)$.

نعرّف توازن تقسيم ما كما يلي: احسب لكل مقطع وسيط المجموعة المتعددة المكونة من جميع عناصره، ثم يكون وسيط المجموعة المتعددة المكونة من هذه الوسائط $k$ هو توازن التقسيم. وبصورة رسمية، للتقسيم $b_1,\ldots,b_{k-1}$، ضع $b_0=0$ و$b_k=n$. وليكن وسيط جميع عناصر المقطع رقم $i$، حيث $0\leq i<k$، هو $c_i=\mathrm{Median}(\{a_{b_i},a_{b_i+1},\ldots,a_{b_{i+1}-1}\})$. عندئذ يكون توازن التقسيم $\mathrm{Median}(\{c_0,\ldots,c_{k-1}\})$.

أوجد أكبر توازن بين جميع التقسيمات.

تفاصيل التنفيذ

لا تحتاج إلى تنفيذ الدالة main، ولا ينبغي لك تنفيذها.

يجب أن يتضمن الملف المصدري الذي تسلمه الترويسة median.h، وذلك بإضافة الكود التالي في بدايته:

#include "median.h"

يجب تنفيذ الدالتين التاليتين في الملف المصدري median.cpp الذي تسلمه:

void init(int c, int t);

• يمثل $c,t$ رقم حالة الاختبار وعدد مجموعات البيانات على التوالي. ويعني $c=0$ أن حالة الاختبار مثال.
• لكل حالة اختبار، يستدعي برنامج التقييم هذه الدالة مرة واحدة بالضبط عند بدء تشغيل البرنامج.

int median(int n, int k, std::vector<int> a);

• تمثل $n,k,a$ طول السلسلة، وعدد مقاطع التقسيم، والسلسلة المعطاة على التوالي.
• يجب أن تعيد هذه الدالة أكبر توازن ممكن.
• لكل حالة اختبار، يستدعي برنامج التقييم هذه الدالة $t$ مرة بالضبط.

الملف template_median.cpp في دليل المسألة كود نموذجي مقدم لك، ويمكنك الرجوع إليه لتنفيذ كودك الخاص.

كيفية اختبار برنامجك

يمكنك استخدام الأمر التالي في دليل المسألة لترجمة البرنامج وإنشاء ملف تنفيذي:

g++ grader.cpp median.cpp -o median -O2 -std=c++14 -static

بالنسبة إلى الملف التنفيذي الناتج median:

سيقرأ من الإدخال القياسي بيانات بالصيغة التالية:

• يحتوي السطر الأول على عددين صحيحين غير سالبين $c,t$.
• تليه مجموعات البيانات بالترتيب. لكل مجموعة بيانات، يحتوي السطر الأول على عددين صحيحين موجبين $n,k$، ويحتوي السطر الثاني على $n$ عدد صحيح موجب $a_0,a_1,\ldots,a_{n-1}$.

سيكتب الملف التنفيذي إلى الإخراج القياسي بيانات بالصيغة التالية:

• لكل مجموعة بيانات، يخرج سطرًا يحتوي على عدد صحيح موجب واحد يمثل أكبر توازن ممكن.

أمثلة

الإدخال 1

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

الإخراج 1

9
8

ملاحظة

للمجموعة الأولى، أحد التقسيمات ذات أكبر توازن هو $b_1=3,b_2=5,b_3=7$، ويقسم السلسلة الأصلية إلى أربعة مقاطع $[6,5,1],[9,2],[3,10],[7,4,8]$. وسائط عناصر هذه المقاطع هي $5,9,10,7$ على التوالي، لذلك توازن هذا التقسيم هو $\mathrm{Median}(\{5,9,10,7\})=9$.

للمجموعة الثانية، أحد التقسيمات ذات أكبر توازن هو $b_1=2,b_2=4,b_3=6,b_4=8$، ويقسم السلسلة الأصلية إلى خمسة مقاطع $[5,7],[3,10],[8,2],[9,1],[6,4]$. وسائط عناصر هذه المقاطع هي $7,10,8,9,6$ على التوالي، لذلك توازن هذا التقسيم هو $\mathrm{Median}(\{7,10,8,9,6\})=8$.

مثال 2

راجع الملفين median/median2.in وmedian/median2.ans في دليل المتسابق.

يحقق هذا المثال قيود حالة الاختبار $6$.

مثال 3

راجع الملفين median/median3.in وmedian/median3.ans في دليل المتسابق.

يحقق هذا المثال قيود حالة الاختبار $9$.

مثال 4

راجع الملفين median/median4.in وmedian/median4.ans في دليل المتسابق.

يحقق هذا المثال قيود حالة الاختبار $14$.

مثال 5

راجع الملفين median/median5.in وmedian/median5.ans في دليل المتسابق.

يحقق هذا المثال قيود حالات الاختبار $18\sim20$.

القيود

لتكن $N$ مجموع قيم $n$ لجميع مجموعات البيانات في حالة اختبار واحدة. لجميع مجموعات البيانات، يتحقق ما يلي:

• $1\leq t\leq 20$.
• $5\leq n\leq 10^6$، و$2\leq k\leq n$، و$N\leq 10^6$.
• لكل $0\leq i<n$، يكون $1\leq a_i\leq n$.

الخاصية الخاصة A: لكل $0\leq i<n$، يكون $a_i\leq 2$.