Untuk multihimpunan $S=\{x_0,x_1,\ldots,x_{m-1}\}$ berukuran $m$, misalkan hasil pengurutan semua elemennya dari terbesar ke terkecil adalah $y_0 \ge y_1 \ge \cdots \ge y_{m-1}$. Definisikan mediannya $\operatorname{Median}(S)$ sebagai elemen terbesar ke-$\lceil m/2\rceil$, yaitu $\operatorname{Median}(S)=y_{\lceil m/2\rceil-1}$. Perhatian: definisi median dalam soal ini mungkin berbeda dari definisi biasa.
Diberikan barisan $[a_0,a_1,\ldots,a_{n-1}]$ sepanjang $n$ dan sebuah bilangan bulat positif $k$ ($k \le n$). Definisikan suatu pembagian sebagai berikut: pilih barisan indeks meningkat $0<b_1<\cdots<b_{k-1}<n$ sepanjang $k-1$. Ini membagi barisan semula menjadi $k$ bagian, dengan interval indeks berturut-turut $[0,b_1),[b_1,b_2),\ldots,[b_{k-1},n)$.
Untuk suatu pembagian, definisikan tingkat keseimbangannya sebagai berikut: untuk setiap bagian, hitung median multihimpunan semua elemen di dalamnya. Median multihimpunan yang terbentuk dari $k$ median tersebut adalah tingkat keseimbangan pembagian itu. Secara formal, untuk pembagian $b_1,\ldots,b_{k-1}$, tetapkan $b_0=0,b_k=n$. Misalkan median multihimpunan semua elemen bagian ke-$i$ ($0 \le i<k$) adalah $c_i=\operatorname{Median}(\{a_{b_i},a_{b_i+1},\ldots,a_{b_{i+1}-1}\})$. Tingkat keseimbangan pembagian tersebut adalah $\operatorname{Median}(\{c_0,\ldots,c_{k-1}\})$.
Tentukan nilai maksimum tingkat keseimbangan di antara semua pembagian.
Detail Implementasi
Peserta tidak perlu dan tidak boleh mengimplementasikan fungsi main.
Peserta harus memastikan bahwa berkas sumber program yang dikumpulkan menyertakan berkas header median.h, yaitu menambahkan kode berikut di awal program:
#include "median.h"Peserta harus mengimplementasikan dua fungsi berikut dalam berkas sumber program median.cpp yang dikumpulkan:
void init(int c, int t);- $c,t$ masing-masing menyatakan nomor kelompok pengujian dan banyaknya kasus uji. $c=0$ menyatakan bahwa kelompok pengujian tersebut adalah contoh.
- Untuk setiap kelompok pengujian, fungsi ini dipanggil tepat satu kali oleh program penilai saat program mulai berjalan.
int median(int n, int k, std::vector<int> a);- $n,k,a$ masing-masing menyatakan panjang barisan, banyaknya bagian pembagian, dan barisan yang diberikan.
- Fungsi ini harus mengembalikan nilai maksimum tingkat keseimbangan.
- Untuk setiap kelompok pengujian, fungsi ini dipanggil tepat $t$ kali oleh program penilai.
Berkas template_median.cpp di direktori soal ini merupakan kode contoh yang disediakan. Peserta dapat menggunakannya sebagai acuan untuk mengimplementasikan kode sendiri.
Cara Menguji Program
Peserta dapat menggunakan perintah berikut di direktori soal untuk mengompilasi berkas eksekutabel:
g++ grader.cpp median.cpp -o median -O2 -std=c++14 -staticUntuk berkas eksekutabel median yang dihasilkan:
Berkas eksekutabel membaca data dari masukan standar dengan format berikut:
- Baris pertama berisi dua bilangan bulat nonnegatif $c,t$.
Berikutnya, kasus uji diberikan secara berurutan. Untuk setiap kasus uji:
- Baris pertama berisi dua bilangan bulat positif $n,k$.
- Baris kedua berisi $n$ bilangan bulat positif $a_0,a_1,\ldots,a_{n-1}$.
Berkas eksekutabel menulis data ke keluaran standar dengan format berikut:
- Untuk setiap kasus uji, keluarkan satu baris berisi sebuah bilangan bulat positif yang menyatakan nilai maksimum tingkat keseimbangan.
Contoh
Masukan 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
Keluaran 1
9 8
Penjelasan
Untuk kasus uji pertama, salah satu pembagian dengan tingkat keseimbangan maksimum adalah $b_1=3,b_2=5,b_3=7$. Pembagian ini membagi barisan semula menjadi 4 bagian $[6,5,1],[9,2],[3,10],[7,4,8]$. Median elemen-elemen setiap bagian masing-masing adalah $5,9,10,7$, sehingga tingkat keseimbangannya adalah $\operatorname{Median}(\{5,9,10,7\})=9$.
Untuk kasus uji kedua, salah satu pembagian dengan tingkat keseimbangan maksimum adalah $b_1=2,b_2=4,b_3=6,b_4=8$. Pembagian ini membagi barisan semula menjadi 5 bagian $[5,7],[3,10],[8,2],[9,1],[6,4]$. Median elemen-elemen setiap bagian masing-masing adalah $7,10,8,9,6$, sehingga tingkat keseimbangannya adalah $\operatorname{Median}(\{7,10,8,9,6\})=8$.
Contoh 2
Lihat median/median2.in dan median/median2.ans di direktori peserta.
Contoh ini memenuhi batasan kelompok pengujian $6$.
Contoh 3
Lihat median/median3.in dan median/median3.ans di direktori peserta.
Contoh ini memenuhi batasan kelompok pengujian $9$.
Contoh 4
Lihat median/median4.in dan median/median4.ans di direktori peserta.
Contoh ini memenuhi batasan kelompok pengujian $14$.
Contoh 5
Lihat median/median5.in dan median/median5.ans di direktori peserta.
Contoh ini memenuhi batasan kelompok pengujian $18 \sim 20$.
Batasan
Misalkan $N$ adalah jumlah nilai $n$ dari semua kasus uji dalam satu kelompok pengujian. Untuk semua kasus uji, berlaku:
- $1 \le t \le 20$;
- $5 \le n \le 10^6$, $2 \le k \le n$, $N \le 10^6$;
- Untuk setiap $0 \le i<n$, berlaku $1 \le a_i \le n$.
| Nomor kelompok pengujian | $N \le$ | $n \le$ | $k$ | Sifat khusus |
|---|---|---|---|---|
| $1,2$ | $40$ | $20$ | $\le n$ | Tidak ada |
| $3 \sim 5$ | $800$ | $80$ | $\le n$ | A |
| $6$ | $800$ | $80$ | $\le n$ | Tidak ada |
| $7,8$ | $8{,}000$ | $800$ | $\le n$ | A |
| $9$ | $8{,}000$ | $800$ | $\le n$ | Tidak ada |
| $10$ | $2 \times 10^5$ | $2 \times 10^5$ | $=2$ | Tidak ada |
| $11$ | $2 \times 10^5$ | $2 \times 10^5$ | $=3$ | Tidak ada |
| $12,13$ | $2 \times 10^5$ | $2 \times 10^5$ | $=5$ | Tidak ada |
| $14$ | $2 \times 10^5$ | $2 \times 10^5$ | $\le 10$ | Tidak ada |
| $15$ | $2 \times 10^5$ | $2 \times 10^5$ | $\equiv 0 \pmod 2$ | Tidak ada |
| $16,17$ | $10^6$ | $10^6$ | $>5$ | Tidak ada |
| $18 \sim 20$ | $10^6$ | $10^6$ | $\le n$ | Tidak ada |
Sifat khusus A: untuk setiap $0 \le i<n$, berlaku $a_i \le 2$.