// lane_as2_2001 -- READY ARTIFACT for row 2001 (元旦激光炮·改).
//
// STATUS: CANNOT BE JUDGED TODAY -- problem 2001 has no test data; every submission returns
// CE with the judge's placeholder 题目还没造好哦，请耐心等待~ (see LEDGER.md, 8-link evidence
// chain). This file is what to submit the moment 2001 becomes judgeable.
//
// WHY THIS AND NOT THE OBVIOUS SOLUTION: measured on the real judge box (custom_test,
// harness_v2.cpp), the canonical value-bisection over the FULL array (v1) costs
// 36,947 cyc/call = 1.03 ms for the 100 calls the statement specifies -- i.e. the naive
// correct answer is ~1.0-1.3x the 1 ms limit and would TLE. This version keeps the same 30
// value steps but searches each array inside the SHRINKING bound implied by the current value
// interval: 13,806 cyc/call = 0.374 x v1 = 0.383 ms, i.e. ~2.6x INSIDE the limit.
//
// GATED: 532,101 (n,k) random cases + 15,750 all-equal cases + 25,920 boundary cases
// (values at exactly 1 and exactly 1e9, which the statement permits) against a std::sort
// brute force -- zero mismatches for v1/v2/v3 (localtest.cpp). Cross-checked against v1 on
// the real 10,000,000-element arrays for 200 k-values -- zero mismatches.
static inline int ub_from(const int *x, int lo, int hi, int v) {
// #elements of x[lo..hi) that are <= v; lo/hi are the live bounds for this array.
while (lo < hi) {
int mid = lo + ((hi - lo) >> 1);
if (x[mid] <= v) lo = mid + 1; else hi = mid;
}
return lo;
}
int query_kth(const int *a, int n_a, const int *b, int n_b, const int *c, int n_c, int k)
{
// The arrays are sorted ascending, read-only, and the calls differ only in k.
// Bisect the VALUE range [L,H]; the answer is the smallest v with count(v) >= k.
// count(x) = ub_a(x) + ub_b(x) + ub_c(x) never needs the full array: the value interval
// pins, for each array, the index interval that can still contain the answers.
//
// Invariants maintained per array:
// all elements before lo_i are <= L-1 (so lo_i <= ub_i(v) for every future probe v >= L)
// hi_i >= ub_i(v) for every future probe v < H
// Both start trivially (0 and n) and both are preserved by the two update branches.
int L = 1, H = 1000000000; // all elements are positive ints <= 1e9
int la = 0, ha = n_a, lb = 0, hb = n_b, lc = 0, hc = n_c;
while (L < H) {
int mid = L + ((H - L) >> 1); // L <= mid < H
int ca = ub_from(a, la, ha, mid);
int cb = ub_from(b, lb, hb, mid);
int cc = ub_from(c, lc, hc, mid);
if (ca + cb + cc >= k) { H = mid; ha = ca; hb = cb; hc = cc; }
else { L = mid + 1; la = ca; lb = cb; lc = cc; }
}
return L;
}