洛谷 P1923 【深基9.例4】求第 k 小的数

// P1923 【深基9.例4】求第 k 小的数 —— 能 AC 的那一版
//
// 两件事都得做对，缺一个就挂：
//   ① ★ **读入**：n 到 5×10⁶、aᵢ 到 10⁹ ⇒ 输入大约 **48 MB**。
//      这是全书最大的一次读入量，`cin`（哪怕关了同步）都吃不下 —— 见 p1923Read.cpp。
//   ② 快速选择：每次划分完只往**一边**走 ⇒ 期望 O(n)（工作量 n + n/2 + n/4 + … = 2n）。
//
// ⚠ 题面说「最小的数是第 **0** 小」—— k 是**从 0 开始**的。样例就能把这一位差抓出来。
// ⚠ pivot 必须随机取，否则有序数据把它卡成 O(n²) ⇒ n = 5×10⁶ 时是 1.25×10¹³ 次。
//   （[第 10 章 P1177](/sol/p1177/) 整页都在说这件事，这里只是后果更重。）

#include <bits/stdc++.h>
using namespace std;

static const int MAXN = 5000005;
static int a[MAXN];

/* ---- fread 快读：一次把整份输入吞进来 ---- */
/* ---- fread 快读：4 MB 的窗口，读完就**续**（不是一次性把整份吞进来）----
   ⚠ 一次性吞的写法必须保证缓冲区 >= 输入字节数，而这道题顶格是 49.4 MB ——
     开小了会**静默**少读一截，见解析页第 ⑤ 步（我自己在这一页上踩的）。 */
static char ibuf[1 << 22];
static size_t ipos = 0, ilen = 0;
static inline int gc() {
    if (ipos == ilen) { ilen = fread(ibuf, 1, sizeof(ibuf), stdin); ipos = 0; if (!ilen) return -1; }
    return ibuf[ipos++];
}
static inline int readInt() {
    int c = gc(), x = 0;
    while (c != -1 && (c < '0' || c > '9')) c = gc();
    for (; c >= '0' && c <= '9'; c = gc()) x = x * 10 + (c - '0');
    return x;
}

static mt19937 rng(20260827u);

/** a[l..r] 里第 k 小（k 从 0 数，相对整段而言的下标） */
static int quickSelect(int l, int r, int k) {
    while (l < r) {
        int p = a[l + (int)(rng() % (unsigned)(r - l + 1))];
        int i = l, j = r, m = l;                 // 三路划分：< p | == p | > p
        while (m <= j) {
            if (a[m] < p)      swap(a[i++], a[m++]);
            else if (a[m] > p) swap(a[m], a[j--]);
            else               m++;
        }
        if (k < i)      r = i - 1;               // 只往一边走
        else if (k > j) l = j + 1;
        else            return p;                // 落在「等于 p」那一段里
    }
    return a[l];
}

int main() {
    int n = readInt(), k = readInt();
    for (int i = 0; i < n; i++) a[i] = readInt();
    printf("%d\n", quickSelect(0, n - 1, k));    // ★ k 从 0 数，不用减 1
    return 0;
}

// P1923 ⚠ 错法一：把 k 当成「第 k 小，从 1 数」
//
// 题面第一句就写着「**最小的数是第 0 小**」，而绝大多数「第 k 小」的模板题是从 1 数的。
// 顺手把模板搬过来，就会写成 `a[k - 1]`（或者 quickSelect(..., k - 1)）。
//
// ★ 这个错**样例就抓得到**：样例是 `5 1 / 4 3 2 1 5`，排好序是 1 2 3 4 5，
//   第 0 小是 1、第 1 小是 2 —— 题面给的答案是 **2**，而这一版给 1。
//   ⇒ [第 8 章 P2249](/sol/p2249/) 那条的又一次：**样例有时候比对拍还狠。**
//
// ⚠ 但它也有抓不到的时候：k = 0 那一档它会读到 a[-1]，行为完全没定义 ——
//   而那一档在题面里是**合法输入**（`0 <= k`）。

#include <bits/stdc++.h>
using namespace std;

static const int MAXN = 5000005;
static int a[MAXN];

/* ---- fread 快读：4 MB 的窗口，读完就**续**（不是一次性把整份吞进来）----
   ⚠ 一次性吞的写法必须保证缓冲区 >= 输入字节数，而这道题顶格是 49.4 MB ——
     开小了会**静默**少读一截，见解析页第 ⑤ 步（我自己在这一页上踩的）。 */
static char ibuf[1 << 22];
static size_t ipos = 0, ilen = 0;
static inline int gc() {
    if (ipos == ilen) { ilen = fread(ibuf, 1, sizeof(ibuf), stdin); ipos = 0; if (!ilen) return -1; }
    return ibuf[ipos++];
}
static inline int readInt() {
    int c = gc(), x = 0;
    while (c != -1 && (c < '0' || c > '9')) c = gc();
    for (; c >= '0' && c <= '9'; c = gc()) x = x * 10 + (c - '0');
    return x;
}

int main() {
    int n = readInt(), k = readInt();
    for (int i = 0; i < n; i++) a[i] = readInt();
    sort(a, a + n);
    printf("%d\n", a[k == 0 ? 0 : k - 1]);       // ⚠ 就是这里（k = 0 时挡一下，免得越界）
    return 0;
}

// P1923 的第一道门槛：把 5×10⁶ 个数读进来
//
// 用法：./p1923Read [n]           人话版（默认题面顶格 n = 5×10⁶）
//       ./p1923Read [n] csv       给 check:viz 用
//
// ★ 先算一笔账（[第 10 章 P1271](/sol/p1271/) 那把尺子：**字节数**，不是数的个数）：
//   n = 5×10⁶ 个数、每个 aᵢ < 10⁹ ⇒ 平均 9 位多 + 一个分隔符 ≈ **每个数 10 字节**
//   ⇒ 输入大约 **48 MB**。这是全书最大的一次读入。
//
// ⚠ 这份程序自己造数据写进临时文件，再 freopen 回来读 —— 不需要喂输入。
// ⚠ 「同步开着」那一趟必须排最前面（关掉同步之后 cin 会预读，换文件会读到残渣）。

#include <bits/stdc++.h>
#include <chrono>
using namespace std;
using namespace std::chrono;

static char path[64];

static void makeData(int nn) {
    snprintf(path, sizeof(path), "/tmp/p1923-bench-%d.txt", (int)getpid());
    FILE* f = fopen(path, "w");
    if (!f) { fprintf(stderr, "写不出临时文件\n"); exit(1); }
    mt19937 rng(20260827u);
    fprintf(f, "%d %d\n", nn, nn / 2);
    for (int i = 0; i < nn; i++)
        fprintf(f, "%u%c", (unsigned)(rng() % 999999999u) + 1, i + 1 == nn ? '\n' : ' ');
    fclose(f);
}
static void reopenIn() { if (!freopen(path, "r", stdin)) { fprintf(stderr, "读不回临时文件\n"); exit(1); } }

static char ibuf[1 << 22];
static size_t ipos = 0, ilen = 0;
static inline int gc() {
    if (ipos == ilen) { ilen = fread(ibuf, 1, sizeof(ibuf), stdin); ipos = 0; if (!ilen) return EOF; }
    return ibuf[ipos++];
}
static inline int readIntFast() {
    int c = gc(), x = 0;
    while (c != EOF && (c < '0' || c > '9')) c = gc();
    for (; c >= '0' && c <= '9'; c = gc()) x = x * 10 + (c - '0');
    return x;
}

int main(int argc, char** argv) {
    int n = (argc > 1) ? atoi(argv[1]) : 5000000;
    bool csv = (argc > 2 && string(argv[2]) == "csv");
    makeData(n);

    long long bytes = 0;
    { FILE* f = fopen(path, "rb"); fseek(f, 0, SEEK_END); bytes = ftell(f); fclose(f); }
    double mb = (double)bytes / 1048576.0;

    double ms[4]; long long sum[4];
    const char* NAME[4] = { "cin 默认（同步开着）", "cin 关同步", "scanf", "fread 快读" };

    { reopenIn(); auto t0 = steady_clock::now(); long long s = 0;
      int nn, kk; cin >> nn >> kk; for (int i = 0; i < n; i++) { int x; cin >> x; s += x; }
      ms[0] = duration<double, milli>(steady_clock::now() - t0).count(); sum[0] = s; }

    { reopenIn(); ios::sync_with_stdio(false); cin.tie(nullptr);
      auto t0 = steady_clock::now(); long long s = 0;
      int nn, kk; cin >> nn >> kk; for (int i = 0; i < n; i++) { int x; cin >> x; s += x; }
      ms[1] = duration<double, milli>(steady_clock::now() - t0).count(); sum[1] = s; }

    { reopenIn(); auto t0 = steady_clock::now(); long long s = 0;
      int nn, kk; if (scanf("%d %d", &nn, &kk) != 2) return 1;
      for (int i = 0; i < n; i++) { int x; if (scanf("%d", &x) != 1) return 1; s += x; }
      ms[2] = duration<double, milli>(steady_clock::now() - t0).count(); sum[2] = s; }

    { reopenIn(); ipos = ilen = 0; auto t0 = steady_clock::now(); long long s = 0;
      readIntFast(); readIntFast(); for (int i = 0; i < n; i++) s += readIntFast();
      ms[3] = duration<double, milli>(steady_clock::now() - t0).count(); sum[3] = s; }

    remove(path);
    bool same = (sum[0] == sum[1] && sum[1] == sum[2] && sum[2] == sum[3]);

    if (csv) {
        printf("n,%d\nbytesMB,%d\nsame,%d\n", n, (int)mb, same ? 1 : 0);
        for (int i = 0; i < 4; i++) printf("ms%d,%.0f\n", i, ms[i]);
        printf("cinOverLimit,%d\n", (ms[0] > 1000.0) ? 1 : 0);
        printf("syncOffOverLimit,%d\n", (ms[1] > 1000.0) ? 1 : 0);
        printf("scanfOverLimit,%d\n", (ms[2] > 1000.0) ? 1 : 0);
        printf("fastUnder200,%d\n", (ms[3] < 200.0) ? 1 : 0);
        printf("syncOffBeatsScanf,%d\n", (ms[1] < ms[2]) ? 1 : 0);
        printf("ratio,%d\n", (int)(ms[0] / ms[3]));
        return 0;
    }

    printf("n = %d，输入文件 %.1f MB（每个数约 %.1f 字节）\n\n", n, mb, (double)bytes / n);
    for (int i = 0; i < 4; i++)
        printf("  %-22s %8.0f 毫秒%s\n", NAME[i], ms[i], (ms[i] > 1000.0) ? "   ✗ 光读就超时了" : "");
    printf("\n  四种读法的校验和%s。最慢 / 最快 = %.1f 倍。\n",
           same ? "完全一致" : "居然不一样！", ms[0] / max(0.001, ms[3]));
    printf("  ⇒ 时限 1 秒。★ **分界线正好落在「默认 cin」和「关掉同步」之间** ——\n");
    printf("    默认 cin 光读就超时，而关掉同步之后它反而比 scanf 还快。\n");
    printf("    ⇒ 「要不要快读」不是一个是非题，是从四档里挑一档；挑之前先把字节数乘出来。\n");
    return 0;
}

// P1923 第 ② 版：拿一个大小 k+1 的**大根堆**来求第 k 小
//
// 这是「求第 k 小」最常被推荐的做法，而且推荐语通常是这么写的：
//   「只要 O(n log k)，比排序的 O(n log n) 好。」
//
// ★ 而这句话**漏了主语**：`k` 是**输入的一部分**，你控制不了。
//   · k = 0            ⇒ 堆里只有一个元素，几乎就是一遍扫描，**四种做法里最快**；
//   · k = n/2          ⇒ ★ **它自己最慢的那一档**（比 k = 0 慢几十倍）。
//
// ⚠ 注意最慢的**不是** k = n-1：那时堆装得下整个数组，全程只有插入、
//   没有「换掉堆顶再下沉」，反而比 k = n/2 快好几倍。
//   ⇒ **最坏的 k 不在端点上** —— 这一条是量出来的，不是推出来的（见 p1923Count.cpp）。
//
// ⇒ 题面写的是 `0 <= k < n`，也就是说**最坏的那个 k 一定会被出到**。

#include <bits/stdc++.h>
using namespace std;

static const int MAXN = 5000005;

/* ---- fread 快读：4 MB 的窗口，读完就**续**（不是一次性把整份吞进来）----
   ⚠ 一次性吞的写法必须保证缓冲区 >= 输入字节数，而这道题顶格是 49.4 MB ——
     开小了会**静默**少读一截，见解析页第 ⑤ 步（我自己在这一页上踩的）。 */
static char ibuf[1 << 22];
static size_t ipos = 0, ilen = 0;
static inline int gc() {
    if (ipos == ilen) { ilen = fread(ibuf, 1, sizeof(ibuf), stdin); ipos = 0; if (!ilen) return -1; }
    return ibuf[ipos++];
}
static inline int readInt() {
    int c = gc(), x = 0;
    while (c != -1 && (c < '0' || c > '9')) c = gc();
    for (; c >= '0' && c <= '9'; c = gc()) x = x * 10 + (c - '0');
    return x;
}

static int heap_[MAXN];                 // 手写大根堆，省掉 priority_queue 的开销

int main() {
    int n = readInt(), k = readInt();
    int cap = k + 1, sz = 0;            // 堆里始终保留「目前最小的 k+1 个」，堆顶是它们里最大的
    for (int i = 0; i < n; i++) {
        int x = readInt();
        if (sz < cap) {
            int c = sz++;               // 上浮
            heap_[c] = x;
            while (c > 0 && heap_[(c - 1) / 2] < heap_[c]) { swap(heap_[(c - 1) / 2], heap_[c]); c = (c - 1) / 2; }
        } else if (x < heap_[0]) {
            heap_[0] = x;               // 换掉堆顶再下沉
            int c = 0;
            while (true) {
                int l = 2 * c + 1, r = l + 1, big = c;
                if (l < sz && heap_[l] > heap_[big]) big = l;
                if (r < sz && heap_[r] > heap_[big]) big = r;
                if (big == c) break;
                swap(heap_[c], heap_[big]); c = big;
            }
        }
    }
    printf("%d\n", heap_[0]);           // 堆顶就是第 k 小（k 从 0 数）
    return 0;
}

// ★★★ 「谁更快」的主语是 k —— 而 k 是出题人给的
//
// 用法：./p1923Count [n]        人话版（默认 n = 10⁶）
//       ./p1923Count [n] csv    给 check:viz 用
//
// 同一份数组、同一台机器，只改一个东西：**要第几小**。四种做法各跑一遍。
//
//   · 快速选择（随机 pivot + 三路）：每次只往一边走 ⇒ 期望 O(n)，**和 k 无关**；
//   · sort 之后取第 k 个：O(n log n)，**也和 k 无关**；
//   · 大小 k+1 的大根堆：O(n log k) —— ★ **只有它跟着 k 变**；
//   · nth_element：库里的 introselect（题面让你别用，这里只当对照）。
//
// ⇒ 题面写的是 `0 <= k < n`，也就是说**最坏的那个 k 一定会被出到**。
//   「O(n log k) 比 O(n log n) 好」这句话，在 k = n-1 那一档是句空话。

#include <bits/stdc++.h>
#include <chrono>
using namespace std;
using namespace std::chrono;

static vector<int> base_, work;
static long long qsOps = 0;

static mt19937 rng(20260827u);
static int quickSelect(int l, int r, int k) {
    while (l < r) {
        int p = work[l + (int)(rng() % (unsigned)(r - l + 1))];
        int i = l, j = r, m = l;
        while (m <= j) {
            qsOps++;
            if (work[m] < p)      swap(work[i++], work[m++]);
            else if (work[m] > p) swap(work[m], work[j--]);
            else                  m++;
        }
        if (k < i)      r = i - 1;
        else if (k > j) l = j + 1;
        else            return p;
    }
    return work[l];
}

static int heapKth(const vector<int>& a, int k) {
    int cap = k + 1;
    vector<int> h; h.reserve(cap);
    for (int x : a) {
        if ((int)h.size() < cap) { h.push_back(x); push_heap(h.begin(), h.end()); }
        else if (x < h.front()) { pop_heap(h.begin(), h.end()); h.back() = x; push_heap(h.begin(), h.end()); }
    }
    return h.front();
}

int main(int argc, char** argv) {
    int n = (argc > 1) ? atoi(argv[1]) : 1000000;
    bool csv = (argc > 2 && string(argv[2]) == "csv");

    base_.resize(n);
    { mt19937 g(20240612u); for (int i = 0; i < n; i++) base_[i] = (int)(g() % 999999999u) + 1; }

    int ks[4] = { 0, n / 100, n / 2, n - 1 };
    const char* kname[4] = { "k = 0", "k = n/100", "k = n/2", "k = n-1" };
    double ms[4][4]; int ans[4][4]; long long ops[4];
    bool same = true;

    for (int t = 0; t < 4; t++) {
        int k = ks[t];
        work = base_; qsOps = 0;
        auto t0 = steady_clock::now();
        ans[t][0] = quickSelect(0, n - 1, k);
        ms[t][0] = duration<double, milli>(steady_clock::now() - t0).count();
        ops[t] = qsOps;

        work = base_;
        t0 = steady_clock::now();
        sort(work.begin(), work.end());
        ans[t][1] = work[k];
        ms[t][1] = duration<double, milli>(steady_clock::now() - t0).count();

        t0 = steady_clock::now();
        ans[t][2] = heapKth(base_, k);
        ms[t][2] = duration<double, milli>(steady_clock::now() - t0).count();

        work = base_;
        t0 = steady_clock::now();
        nth_element(work.begin(), work.begin() + k, work.end());
        ans[t][3] = work[k];
        ms[t][3] = duration<double, milli>(steady_clock::now() - t0).count();

        for (int i = 1; i < 4; i++) if (ans[t][i] != ans[t][0]) same = false;
    }

    /* 结论量（不钉毫秒，钉「谁快谁慢」和倍数） */
    int heapBestAt0 = 1;                       // k = 0 那一行，堆是四种里最快的
    for (int i = 0; i < 4; i++) if (i != 2 && ms[0][2] > ms[0][i]) heapBestAt0 = 0;
    int heapPeak = 0;                          // 堆自己最慢的是哪一个 k
    for (int t = 1; t < 4; t++) if (ms[t][2] > ms[heapPeak][2]) heapPeak = t;
    int heapRatio = (int)(ms[2][2] / max(0.001, ms[0][2]));
    int qsSteady = 1;                          // 快速选择的比较次数四档都不到 4n
    for (int t = 0; t < 4; t++) if (ops[t] >= 4LL * n) qsSteady = 0;
    int heapSlowerThanQsAtMid = (ms[2][2] > ms[2][0] * 2) ? 1 : 0;

    if (csv) {
        printf("n,%d\nsame,%d\n", n, same ? 1 : 0);
        printf("heapBestAt0,%d\nheapPeakIdx,%d\nheapRatio,%d\nqsUnder4n,%d\nheapSlowerThanQsAtMid,%d\n",
               heapBestAt0, heapPeak, heapRatio, qsSteady, heapSlowerThanQsAtMid);
        for (int t = 0; t < 4; t++) printf("qsOps%d,%lld\n", t, ops[t]);
        return 0;
    }

    printf("n = %d，同一份随机数组，只改「要第几小」：\n\n", n);
    printf("  %-10s %12s %12s %12s %12s\n", "", "快速选择", "sort", "大小k+1的堆", "nth_element");
    printf("  %-10s %12s %12s %12s %12s\n", "----------", "------------", "------------", "------------", "------------");
    for (int t = 0; t < 4; t++) {
        printf("  %-10s", kname[t]);
        for (int i = 0; i < 4; i++) printf(" %9.1f ms", ms[t][i]);
        printf("\n");
    }
    printf("\n  四行四列的答案%s。\n", same ? "全部相同" : "居然不一样！");
    printf("\n  ★ 只看「堆」那一列：k = 0 时 %.1f 毫秒（**四种里最快**），%s 时 %.1f 毫秒 —— 差 %d 倍。\n",
           ms[0][2], kname[heapPeak], ms[heapPeak][2], heapRatio);
    printf("    ⚠ 而它最慢的那一档**不在端点上**：k = n-1 是 %.1f 毫秒，比 k = n/2 的 %.1f 还快。\n",
           ms[3][2], ms[2][2]);
    printf("    而快速选择那一列几乎是一条直线：比较次数 %lld / %lld / %lld / %lld（都不到 4n）。\n",
           ops[0], ops[1], ops[2], ops[3]);
    printf("\n  ⇒ 「O(n log k) 比 O(n log n) 好」这句话**没有主语就是错的** ——\n");
    printf("    主语是 k，而 k 写在输入里，题面保证 0 <= k < n。**最坏的那个 k 一定会被出到。**\n");
    return 0;
}

// ⚠ P1923 —— 我自己在写这一页时踩的那个坑，留一份现场
//
// 和 p1923.cpp 只差一处：快读用的是「**一次性把整份输入吞进一个静态数组**」的写法，
// 而那个数组开了 `1 << 25` = **33 554 432 字节 ≈ 33.5 MB**。
//
// 这道题顶格的输入是 **49.4 MB**。
// ⇒ fread 只吞进前 33.5 MB，剩下约 1.6×10⁶ 个数**根本没读到**，
//   它们留在数组里是 0 —— 而 0 比题面允许的最小值（1）还小，于是排序后全挤在最前面。
//
// ★★★ 最要命的是它**一声不吭**：
//   · 没有报错、没有崩溃；
//   · 而我当时**五个版本用的是同一份错误的快读** ⇒ 五个版本一起错，
//     **对拍 0 次不一致**（[第 9 章 P1182](/sol/p1182/) 那条：两边错得一样，对拍就是瞎的）。
//
// ⇒ 缓冲区够不够是一道算术题，尺子还是[第 10 章 P1271](/sol/p1271/) 那把：**字节数**。
//   而更稳的写法是根本不去算它 —— 用「读完就续」的 4 MB 窗口（p1923.cpp 里那份）。

#include <bits/stdc++.h>
using namespace std;

static const int MAXN = 5000005;
static int a[MAXN];

static char buf[1 << 25];                        // ⚠ 33.5 MB，而输入有 49.4 MB
static int bufLen = 0, bufPos = 0;
static inline int readInt() {
    while (bufPos < bufLen && (buf[bufPos] < '0' || buf[bufPos] > '9')) bufPos++;
    int x = 0;
    while (bufPos < bufLen && buf[bufPos] >= '0' && buf[bufPos] <= '9')
        x = x * 10 + (buf[bufPos++] - '0');
    return x;
}

int main() {
    bufLen = (int)fread(buf, 1, sizeof(buf), stdin);
    int n = readInt(), k = readInt();
    for (int i = 0; i < n; i++) a[i] = readInt();
    sort(a, a + n);
    printf("%d\n", a[k]);
    return 0;
}

// 数据生成器（P1923 对拍用）：`./p1923Gen <seed> [level] [n]`
//
//   level 0（默认）★ **照题面**：n 是**奇数**，aᵢ ∈ [1, 10⁹)，k 随机
//   level 1        ★★ **n 取偶数** —— 故意**违反**题面那条「n 为奇数」的保证。
//                  这一档存在的唯一理由是：**验一验那条保证到底有没有用。**
//   level 2        已经升序 / 完全倒序 / 全部相同（专抓 pivot 取首元素那一版）
//   level 3        k 顶到两个端点（k = 0 或 k = n-1）＋ 值域压到 1..3（大量重复）
//
// ★ 题面里的每一条保证都值得问一句「它挡掉了什么」：
//   · P1908 的「注意序列中可能有重复数字」是**情报** —— 它指的正是随机数据造不出来的那一档；
//   · 这道题的「n 为奇数」呢？level 1 就是用来回答这个问题的。
//     （答案在解析页第 ⑥ 步：五个版本在这一档上和照题面那一档**表现完全一样**。）

#include <bits/stdc++.h>
using namespace std;
static mt19937 rng;
static int ri(int lo, int hi) { return lo + (int)(rng() % (unsigned)(hi - lo + 1)); }

int main(int argc, char** argv) {
    rng.seed((argc > 1) ? (unsigned)atoi(argv[1]) : 1);
    int level = (argc > 2) ? atoi(argv[2]) : 0;

    int n = ri(1, 15);
    if (level == 1) { if (n % 2 == 1) n++; }              // ★ 偶数（违反题面）
    else            { if (n % 2 == 0) n++; }              // 照题面：奇数
    if (argc > 3) n = atoi(argv[3]);

    int hi = (level == 3) ? 3 : (ri(0, 1) ? 20 : 999999999);
    vector<int> a(n);
    for (int i = 0; i < n; i++) a[i] = ri(1, hi);
    if (level == 2) {
        int m = ri(0, 2);
        if (m == 0) sort(a.begin(), a.end());
        else if (m == 1) sort(a.begin(), a.end(), greater<int>());
        else for (int i = 0; i < n; i++) a[i] = 7;
    }

    int k = (level == 3) ? (ri(0, 1) ? 0 : n - 1) : ri(0, n - 1);
    printf("%d %d\n", n, k);
    for (int i = 0; i < n; i++) printf("%d%c", a[i], i + 1 == n ? '\n' : ' ');
    return 0;
}

// P1923 ⚠ 错法二：手写快速选择，但 pivot 取当前段的第一个元素
//
// 这条[第 10 章 P1177](/sol/p1177/) 整页都在说，这里只补一个数：**后果重多少**。
//   · P1177 的 n = 10⁵ ⇒ 退化后 5×10⁹ 次比较，端到端 1511 毫秒（时限 1 秒）；
//   · 这道题的 n = 5×10⁶ ⇒ 退化后 **1.25×10¹³** 次 —— 差 **2500 倍**，
//     而且递归深度也是 n 级别，栈先炸。
//
// ⚠ 它在**随机数据**上完全正常（和 P1177 一样：本地随手测，它甚至更快）——
//   顶格随机数据上它和正解差不多，所以页面上量退化用的是**有序**数据，而且只量到
//   n = 2×10⁵ 再按平方外推：真喂顶格有序数据给它，要跑几个小时。

#include <bits/stdc++.h>
using namespace std;

static const int MAXN = 5000005;
static int a[MAXN];

/* ---- fread 快读：4 MB 的窗口，读完就**续**（不是一次性把整份吞进来）----
   ⚠ 一次性吞的写法必须保证缓冲区 >= 输入字节数，而这道题顶格是 49.4 MB ——
     开小了会**静默**少读一截，见解析页第 ⑤ 步（我自己在这一页上踩的）。 */
static char ibuf[1 << 22];
static size_t ipos = 0, ilen = 0;
static inline int gc() {
    if (ipos == ilen) { ilen = fread(ibuf, 1, sizeof(ibuf), stdin); ipos = 0; if (!ilen) return -1; }
    return ibuf[ipos++];
}
static inline int readInt() {
    int c = gc(), x = 0;
    while (c != -1 && (c < '0' || c > '9')) c = gc();
    for (; c >= '0' && c <= '9'; c = gc()) x = x * 10 + (c - '0');
    return x;
}

/** pivot = a[l]，单向 partition —— 有序数据上一次只切掉一个元素 */
static int quickSelectBad(int l, int r, int k) {
    while (l < r) {
        int p = a[l], i = l, j = r;
        while (i < j) {
            while (i < j && a[j] >= p) j--;
            a[i] = a[j];
            while (i < j && a[i] <= p) i++;
            a[j] = a[i];
        }
        a[i] = p;
        if (k < i) r = i - 1;
        else if (k > i) l = i + 1;
        else return p;
    }
    return a[l];
}

int main() {
    int n = readInt(), k = readInt();
    for (int i = 0; i < n; i++) a[i] = readInt();
    printf("%d\n", quickSelectBad(0, n - 1, k));
    return 0;
}