Background

The statement and sample attachments come from QOJ。

When submitting to Luogu, there is no need to include the header #include "median.h"。Just copy

void init(int c, int t);
int median(int n, int k, std::vector<int> a);

to the beginning of your program, and compile with a C++17 or higher compiler。

Problem Description

For a multiset $S=\{x_0,x_1,\ldots,x_{m-1}\}$ of size $m$, let the result of sorting all its elements from large to small be $y_0\ge y_1\ge\cdots\ge y_{m-1}$。Define its median $\operatorname{Median}(S)$ as the $\left\lceil\frac{m}{2}\right\rceil$-th largest number, i.e., $\operatorname{Median}(S)=y_{\left\lceil\frac{m}{2}\right\rceil-1}$。Note: the definition of median in this problem may be different from the usual definition。

Given a sequence of length $n$, $[a_0,a_1,\ldots,a_{n-1}]$, and a positive integer $k$ ($k\le n$)。Define a partition as follows: choose an increasing index sequence of length $k-1$, $0<b_1<\cdots<b_{k-1}<n$, which partitions the original sequence into $k$ segments, with index intervals (in order) $[0,b_1),[b_1,b_2),\ldots,[b_{k-1},n)$。

For a partition, define its balance value as follows: for each segment in the partition, compute the median of the multiset formed by all elements in that segment; then the median of the multiset of these $k$ medians is the balance value of this partition。Formally, for a partition $b_1,\ldots,b_{k-1}$, let $b_0=0$ and $b_k=n$。Let the median of the multiset of all elements in the $i$-th segment ($0\le i<k$) be $c_i=\operatorname{Median}(\{a_{b_i},a_{b_i+1},\ldots,a_{b_{i+1}-1}\})$。Then the balance value of this partition is $\operatorname{Median}(\{c_0,\ldots,c_{k-1}\})$。

Please find the maximum balance value among all partitions。

【Implementation Details】

Contestants do not need to, and should not, implement the main function。

Contestants need to ensure the submitted source file includes the header median.h, i.e., add the following code at the beginning:

#include "median.h"

Contestants need to implement the following two functions in the submitted source file median.cpp:

void init(int c, int t);

• $c,t$ represent the test point ID and the number of testdata groups, respectively。$c=0$ means this test point is the sample。
• For each test point, this function will be called by the grader exactly once when the program starts running。

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

• $n,k,a$ represent the sequence length, the number of segments in the partition, and the given sequence, respectively。
• This function should return the maximum balance value。
• For each test point, this function will be called by the grader exactly $t$ times。

template_median.cpp in this problem directory is the provided sample code。Contestants may refer to it and implement their own code。

Input Format

【Grader Program Method】

Contestants can compile an executable in this problem directory using the following command:

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

For the compiled executable file median:

• The executable will read input from standard input in the following format:
  • The first line contains two non-negative integers $c,t$。
  • Then follow the testdata groups in order。For each testdata group:
    • The first line contains two positive integers $n,k$。
    • The second line contains $n$ positive integers $a_0,a_1,\ldots,a_{n-1}$。
• The executable will output to standard output in the following format:
  • For each testdata group, output one line containing one positive integer, representing the maximum balance value。

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

9
8

Hint

【Sample $1$ Explanation】

For the first testdata group, one partition with the maximum balance value is $b_1=3$，$b_2=5$，$b_3=7$。It partitions the original sequence into $4$ segments $[6,5,1]$、$[9,2]$、$[3,10]$、$[7,4,8]$。The medians of the elements in the segments are $5,9,10,7$ respectively, so the balance value of this partition is $\operatorname{Median}(\{5,9,10,7\})=9$。

For the second testdata group, one partition with the maximum balance value is $b_1=2$，$b_2=4$，$b_3=6$，$b_4=8$。It partitions the original sequence into $5$ segments $[5,7]$、$[3,10]$、$[8,2]$、$[9,1]$、$[6,4]$。The medians of the elements in the segments are $7,10,8,9,6$ respectively, so the balance value of this partition is $\operatorname{Median}(\{7,10,8,9,6\})=8$。

【Sample $2$】

See median/median2.in and median/median2.ans in the contestant directory。

This sample satisfies the constraints of test point $6$。

【Sample $3$】

See median/median3.in and median/median3.ans in the contestant directory。

This sample satisfies the constraints of test point $9$。

【Sample $4$】

See median/median4.in and median/median4.ans in the contestant directory。

This sample satisfies the constraints of test point $14$。

【Sample $5$】

See median/median5.in and median/median5.ans in the contestant directory。

This sample satisfies the constraints of test points $18\sim20$。

【Constraints】

Let $N$ be the sum of $n$ over all testdata within a single test point。For all testdata, we have:

• $1\le t\le20$；
• $5\le n\le10^6$，$2\le k\le n$，$N\le10^6$；
• For all $0\le i<n$, we have $1\le a_i\le n$。

::cute-table{tuack} | Test point ID | $N\le$ | $n\le$ | $k$ | Special property | |:-:|:-:|:-:|:-:|:-:| | $1,2$ | $40$ | $20$ | $\le n$ | None | | $3\sim5$ | $800$ | $80$ | ^ | $A$ | | $6$ | ^ | ^ | ^ | None | | $7,8$ | $8000$ | $800$ | ^ | $A$ | | $9$ | ^ | ^ | ^ | None | | $10$ | $2\times10^5$ | $2\times10^5$ | $=2$ | ^ | | $11$ | ^ | ^ | $=3$ | ^ | | $12,13$ | ^ | ^ | $=5$ | ^ | | $14$ | ^ | ^ | $\le10$ | ^ | | $15$ | ^ | ^ | $\equiv0\pmod 2$ | ^ | | $16,17$ | $10^6$ | $10^6$ | $>5$ | ^ | | $18\sim20$ | ^ | ^ | $\le n$ | ^ |

Special property $A$: for all $0\le i<n$, we have $a_i\le2$。

Translated by ChatGPT 5