Với đa tập $S=\{x_0,x_1,\ldots,x_{m-1}\}$ có kích thước $m$, giả sử các phần tử được sắp theo thứ tự giảm dần thành $y_0\ge y_1\ge\cdots\ge y_{m-1}$. Định nghĩa trung vị $\operatorname{Median}(S)$ là phần tử lớn thứ $\lceil m/2\rceil$, tức là $\operatorname{Median}(S)=y_{\lceil m/2\rceil-1}$. Lưu ý: định nghĩa trung vị trong bài này có thể khác định nghĩa thông thường.

Cho dãy $[a_0,a_1,\ldots,a_{n-1}]$ độ dài $n$ và số nguyên dương $k$ ($k\le n$). Một cách phân chia được định nghĩa như sau: chọn một dãy chỉ số tăng dần có độ dài $k-1$, $0<b_1<\cdots<b_{k-1}<n$, để chia dãy ban đầu thành $k$ đoạn, với các khoảng chỉ số lần lượt là $[0,b_1),[b_1,b_2),\ldots,[b_{k-1},n)$.

Độ cân bằng của một cách phân chia được định nghĩa như sau: với mỗi đoạn, tính trung vị của đa tập gồm tất cả phần tử trong đoạn đó; trung vị của đa tập gồm $k$ trung vị này là độ cân bằng của cách phân chia. Một cách hình thức, với cách chia $b_1,\ldots,b_{k-1}$, đặt $b_0=0,b_k=n$. Gọi trung vị của đa tập các phần tử trong đoạn thứ $i$ ($0\le i<k$) là $c_i=\operatorname{Median}(\{a_{b_i},a_{b_i+1},\ldots,a_{b_{i+1}-1}\})$. Độ cân bằng của cách chia là $\operatorname{Median}(\{c_0,\ldots,c_{k-1}\})$.

Hãy tìm độ cân bằng lớn nhất trong tất cả các cách phân chia.

Chi tiết cài đặt

Bạn không cần và không được cài đặt hàm main.

Mã nguồn nộp phải chứa tệp tiêu đề median.h, tức là thêm đoạn mã sau vào đầu chương trình:

#include "median.h"

Bạn cần cài đặt hai hàm sau trong tệp mã nguồn median.cpp:

void init(int c, int t);

• $c,t$ lần lượt là số hiệu bộ kiểm thử và số bộ dữ liệu kiểm thử. $c=0$ biểu thị bộ kiểm thử là ví dụ.
• Với mỗi bộ kiểm thử, chương trình chấm gọi hàm này đúng một lần khi chương trình bắt đầu chạy.

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

• $n,k,a$ lần lượt là độ dài dãy, số đoạn cần chia và dãy đã cho.
• Hàm phải trả về độ cân bằng lớn nhất.
• Với mỗi bộ kiểm thử, chương trình chấm gọi hàm này đúng $t$ lần.

Tệp template_median.cpp trong thư mục bài này là mã mẫu được cung cấp; bạn có thể tham khảo và cài đặt mã của mình.

Cách kiểm thử chương trình

Bạn có thể dùng lệnh sau trong thư mục bài này để biên dịch thành tệp thực thi:

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

Với tệp thực thi median đã biên dịch:

• Tệp thực thi đọc từ đầu vào chuẩn dữ liệu theo định dạng sau:

  • Dòng đầu tiên chứa hai số nguyên không âm $c,t$.

  • Tiếp theo lần lượt là các bộ dữ liệu. Với mỗi bộ dữ liệu:

    • Dòng đầu tiên chứa hai số nguyên dương $n,k$.

    • Dòng thứ hai chứa $n$ số nguyên dương $a_0,a_1,\ldots,a_{n-1}$.

• Tệp thực thi ghi dữ liệu theo định dạng sau ra đầu ra chuẩn:

  • Với mỗi bộ dữ liệu, in ra một số nguyên dương trên một dòng, là độ cân bằng lớn nhất.

Ví dụ

Dữ liệu vào 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

Dữ liệu ra 1

9
8

Ghi chú

Với bộ dữ liệu thứ nhất, một cách chia có độ cân bằng lớn nhất là $b_1=3,b_2=5,b_3=7$, chia dãy thành 4 đoạn $[6,5,1],[9,2],[3,10],[7,4,8]$. Trung vị của các đoạn lần lượt là $5,9,10,7$, nên độ cân bằng là $\operatorname{Median}(\{5,9,10,7\})=9$.

Với bộ dữ liệu thứ hai, một cách chia có độ cân bằng lớn nhất là $b_1=2,b_2=4,b_3=6,b_4=8$, chia dãy thành 5 đoạn $[5,7],[3,10],[8,2],[9,1],[6,4]$. Trung vị của các đoạn lần lượt là $7,10,8,9,6$, nên độ cân bằng là $\operatorname{Median}(\{7,10,8,9,6\})=8$.

Ví dụ 2

Xem các tệp median/median2.in và median/median2.ans trong thư mục của thí sinh.

Ví dụ này thỏa mãn giới hạn của bộ kiểm thử $6$.

Ví dụ 3

Xem các tệp median/median3.in và median/median3.ans trong thư mục của thí sinh.

Ví dụ này thỏa mãn giới hạn của bộ kiểm thử $9$.

Ví dụ 4

Xem các tệp median/median4.in và median/median4.ans trong thư mục của thí sinh.

Ví dụ này thỏa mãn giới hạn của bộ kiểm thử $14$.

Ví dụ 5

Xem các tệp median/median5.in và median/median5.ans trong thư mục của thí sinh.

Ví dụ này thỏa mãn giới hạn của các bộ kiểm thử $18\sim20$.

Giới hạn

Gọi $N$ là tổng các giá trị $n$ của mọi bộ dữ liệu trong một bộ kiểm thử. Với mọi dữ liệu:

• $1\le t\le20$;
• $5\le n\le10^6$, $2\le k\le n$, $N\le10^6$;
• Với mọi $0\le i<n$, $1\le a_i\le n$.

Tính chất đặc biệt A: Với mọi $0\le i<n$, $a_i\le2$.