Pour un multiensemble $S=\{x_0,x_1,\dots,x_{m-1}\}$ de taille $m$, notons $y_0\ge y_1\ge\dots\ge y_{m-1}$ ses éléments triés par ordre décroissant. On définit sa médiane $\operatorname{Median}(S)$ comme son $\lceil m/2\rceil$-ième plus grand élément, soit $\operatorname{Median}(S)=y_{\lceil m/2\rceil-1}$. Attention : la définition de la médiane utilisée ici peut différer de la définition habituelle.

Une séquence $[a_0,a_1,\dots,a_{n-1}]$ de longueur $n$ et un entier positif $k$ ($k\le n$) sont donnés. Une partition est définie ainsi : choisir une séquence croissante de $k-1$ indices $0<b_1<\dots<b_{k-1}<n$ découpe la séquence initiale en $k$ segments, dont les intervalles d'indices sont respectivement $[0,b_1),[b_1,b_2),\dots,[b_{k-1},n)$.

L'équilibre d'une partition est défini ainsi : pour chaque segment, on calcule la médiane du multiensemble de tous ses éléments ; l'équilibre est alors la médiane du multiensemble de ces $k$ médianes. Formellement, pour une partition $b_1,\dots,b_{k-1}$, posons $b_0=0,b_k=n$ et, pour chaque segment $i$ ($0\le i<k$), $c_i=\operatorname{Median}(\{a_{b_i},a_{b_i+1},\dots,a_{b_{i+1}-1}\})$. L'équilibre de la partition est $\operatorname{Median}(\{c_0,\dots,c_{k-1}\})$.

Déterminez l'équilibre maximal parmi toutes les partitions.

Détails d'implémentation

Vous n'avez pas besoin d'implémenter la fonction main et ne devez pas le faire.

Assurez-vous que le fichier source soumis inclut l'en-tête median.h, en ajoutant au début du programme :

#include "median.h"

Vous devez implémenter les deux fonctions suivantes dans le fichier source soumis median.cpp :

void init(int c, int t);

• $c,t$ représentent respectivement le numéro du test et le nombre de jeux de données. $c=0$ indique un exemple.
• Pour chaque test, cette fonction est appelée exactement une fois par le programme d'évaluation au début de l'exécution.

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

• $n,k,a$ représentent respectivement la longueur de la séquence, le nombre de segments de la partition et la séquence donnée.
• Cette fonction doit renvoyer l'équilibre maximal.
• Pour chaque test, elle est appelée exactement $t$ fois par le programme d'évaluation.

Le fichier template_median.cpp du répertoire du problème contient un exemple de code dont vous pouvez vous inspirer pour écrire votre propre programme.

Test du programme

Vous pouvez utiliser la commande suivante dans le répertoire du problème pour compiler un exécutable :

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

Pour l'exécutable median ainsi obtenu :

• Il lit les données sur l'entrée standard au format suivant :

  • La première ligne contient deux entiers non négatifs $c,t$.

  • Les jeux de données suivent dans l'ordre. Pour chacun :

    • La première ligne contient deux entiers positifs $n,k$.
    • La deuxième ligne contient $n$ entiers positifs $a_0,a_1,\dots,a_{n-1}$.

• Il écrit les données sur la sortie standard au format suivant :

  • Pour chaque jeu de données, une ligne contenant un entier positif représentant l'équilibre maximal.

Exemples

Entrée 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

Sortie 1

9
8

Remarque

Pour le premier jeu de données, une partition d'équilibre maximal est $b_1=3,b_2=5,b_3=7$. Elle découpe la séquence initiale en quatre segments $[6,5,1],[9,2],[3,10],[7,4,8]$, dont les médianes sont respectivement $5,9,10,7$. Son équilibre est donc $\operatorname{Median}(\{5,9,10,7\})=9$.

Pour le deuxième jeu de données, une partition d'équilibre maximal est $b_1=2,b_2=4,b_3=6,b_4=8$. Elle découpe la séquence initiale en cinq segments $[5,7],[3,10],[8,2],[9,1],[6,4]$, dont les médianes sont respectivement $7,10,8,9,6$. Son équilibre est donc $\operatorname{Median}(\{7,10,8,9,6\})=8$.

Exemple 2

Voir les fichiers median/median2.in et median/median2.ans dans le répertoire des candidats.

Cet exemple satisfait les contraintes du test 6.

Exemple 3

Voir les fichiers median/median3.in et median/median3.ans dans le répertoire des candidats.

Cet exemple satisfait les contraintes du test 9.

Exemple 4

Voir les fichiers median/median4.in et median/median4.ans dans le répertoire des candidats.

Cet exemple satisfait les contraintes du test 14.

Exemple 5

Voir les fichiers median/median5.in et median/median5.ans dans le répertoire des candidats.

Cet exemple satisfait les contraintes des tests $18\sim20$.

Contraintes

On note $N$ la somme des valeurs de $n$ de tous les jeux de données d'un même test. Pour tous les jeux de données :

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

Propriété particulière $A$ : pour tout $0\le i<n$, $a_i\le2$.