Ask Amplitude Hallucinations

    1#include <bits/stdc++.h>
    2using namespace std;
    3 
    4struct Node {
    5    int val;
    6    int idx;
    7};
    8 
    9Node better(Node a, Node b) {
    10    if (a.val != b.val) return (a.val > b.val ? a : b);
    11    return (a.idx < b.idx ? a : b); // leftmost on tie
    12}
    13 
    14struct SegTree {
    15    int n;
    16    vector<Node> t;
    17 
    18    SegTree(const string &s) {
    19        n = s.size();
    20        t.resize(4*n);
    21        build(s, 1, 0, n-1);
    22    }
    23 
    24    void build(const string &s, int v, int l, int r) {
    25        if (l == r) {
    26            t[v] = {s[l] - '0', l};
    27            return;
    28        }
    29        int m = (l+r)/2;
    30        build(s, v*2, l, m);
    31        build(s, v*2+1, m+1, r);
    32        t[v] = better(t[v*2], t[v*2+1]);
    33    }
    34 
    35    Node query(int v, int l, int r, int ql, int qr) {
    36        if (qr < l || r < ql) return {-1, INT_MAX};
    37        if (ql <= l && r <= qr) return t[v];
    38        int m = (l+r)/2;
    39        return better(
    40            query(v*2, l, m, ql, qr),
    41            query(v*2+1, m+1, r, ql, qr)
    42        );
    43    }
    44 
    45    Node query(int l, int r) {
    46        return query(1, 0, n-1, l, r);
    47    }
    48};
    49 
    50int main() {
    51    ios::sync_with_stdio(false);
    52    cin.tie(nullptr);
    53 
    54    int k;
    55    string s;
    56    cin >> k >> s;
    57 
    58    int m = s.size();
    59    SegTree st(s);
    60 
    61    int need = k;
    62    int pos = 0;
    63 
    64    vector<char> ans;
    65 
    66    while (need > 0) {
    67 
    68        int max_pick = m - need;   // right boundary of valid window
    69 
    70        Node best = st.query(pos, max_pick);
    71 
    72        ans.push_back(char('0' + best.val));
    73 
    74        pos = best.idx + 1;        // continue after chosen digit
    75        need--;
    76    }
    77 
    78    for (char c : ans) cout << c;
    79    cout << '\n';
    80}
    81