Para um multiconjunto $S=\{x_0,x_1,\ldots,x_{m-1}\}$ de tamanho $m$, sejam $y_0\ge y_1\ge\cdots\ge y_{m-1}$ os seus elementos ordenados do maior para o menor. Define-se a sua mediana $Median(S)$ como o $\lceil m/2\rceil$-ésimo maior elemento, isto é, $Median(S)=y_{\lceil m/2\rceil-1}$. Atenção: a definição de mediana deste problema pode ser diferente da definição habitual.

É dada uma sequência $[a_0,a_1,\ldots,a_{n-1}]$ de comprimento $n$ e um inteiro positivo $k\le n$. Define-se uma partição da seguinte forma: escolhe-se uma sequência crescente de $k-1$ índices $0<b_1<\cdots<b_{k-1}<n$, dividindo a sequência original em $k$ segmentos, cujos intervalos de índices são, por ordem, $[0,b_1),[b_1,b_2),\ldots,[b_{k-1},n)$.

Define-se o equilíbrio de uma partição da seguinte forma: para cada segmento, calcula-se a mediana do multiconjunto formado por todos os seus elementos. O equilíbrio é a mediana do multiconjunto formado por essas $k$ medianas. Formalmente, para a partição $b_1,\ldots,b_{k-1}$, sejam $b_0=0$ e $b_k=n$, e seja $c_i=Median(\{a_{b_i},a_{b_i+1},\ldots,a_{b_{i+1}-1}\})$ a mediana do multiconjunto dos elementos do segmento $i$, para $0\le i<k$. O equilíbrio dessa partição é $Median(\{c_0,\ldots,c_{k-1}\})$.

Determina o maior equilíbrio entre todas as partições.

Detalhes de implementação

Não precisas de implementar a função main, e não a deves implementar.

Garante que o ficheiro de código-fonte submetido inclui o cabeçalho median.h, acrescentando o código seguinte no início do programa:

#include "median.h"

No ficheiro de código-fonte median.cpp que submetes, deves implementar as duas funções seguintes:

void init(int c, int t);

• $c,t$ representam, respetivamente, o número do teste e o número de casos de teste. O valor $c=0$ indica que se trata de um exemplo.
• Para cada teste, o avaliador chama esta função exatamente uma vez, no início da execução do programa.

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

• $n,k,a$ representam, respetivamente, o comprimento da sequência, o número de segmentos da partição e a sequência dada.
• A função deve devolver o maior equilíbrio possível.
• Para cada teste, o avaliador chama esta função exatamente $t$ vezes.

O ficheiro template_median.cpp, no diretório do problema, contém o código de exemplo fornecido. Podes usá-lo como referência para a tua implementação.

Como testar o programa

No diretório do problema, podes usar o comando seguinte para compilar o executável:

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

Para o executável median assim compilado:

• O executável lê da entrada padrão dados no formato seguinte:

  • A primeira linha contém dois inteiros não negativos $c,t$.

  • Seguem-se, por ordem, os casos de teste. Para cada caso:

    • A primeira linha contém dois inteiros positivos $n,k$.
    • A segunda linha contém $n$ inteiros positivos $a_0,a_1,\ldots,a_{n-1}$.

• O executável escreve na saída padrão dados no formato seguinte:

  • Para cada caso, apresenta uma linha com um inteiro positivo que representa o maior equilíbrio possível.

Exemplos

Entrada 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

Saída 1

9
8

Nota

Para o primeiro caso, uma partição de equilíbrio máximo tem $b_1=3$, $b_2=5$ e $b_3=7$. Divide a sequência original nos 4 segmentos $[6,5,1]$, $[9,2]$, $[3,10]$, $[7,4,8]$, cujas medianas são, respetivamente, $5,9,10,7$. Logo, o equilíbrio dessa partição é $Median(\{5,9,10,7\})=9$.

Para o segundo caso, uma partição de equilíbrio máximo tem $b_1=2$, $b_2=4$, $b_3=6$ e $b_4=8$. Divide a sequência original nos 5 segmentos $[5,7]$, $[3,10]$, $[8,2]$, $[9,1]$, $[6,4]$, cujas medianas são, respetivamente, $7,10,8,9,6$. Logo, o equilíbrio dessa partição é $Median(\{7,10,8,9,6\})=8$.

Exemplo 2

Consulta os ficheiros median/median2.in e median/median2.ans no diretório dos concorrentes.

Este exemplo satisfaz as restrições do teste $6$.

Exemplo 3

Consulta os ficheiros median/median3.in e median/median3.ans no diretório dos concorrentes.

Este exemplo satisfaz as restrições do teste $9$.

Exemplo 4

Consulta os ficheiros median/median4.in e median/median4.ans no diretório dos concorrentes.

Este exemplo satisfaz as restrições do teste $14$.

Exemplo 5

Consulta os ficheiros median/median5.in e median/median5.ans no diretório dos concorrentes.

Este exemplo satisfaz as restrições dos testes $18\sim20$.

Restrições

Seja $N$ a soma de $n$ de todos os casos contidos num único teste. Para todos os dados de teste:

• $1\le t\le20$;
• $5\le n\le10^6$, $2\le k\le n$, $N\le10^6$;
• Para todo o $0\le i<n$, $1\le a_i\le n$.

Propriedade especial A: para todo o $0\le i<n$, $a_i\le2$.