set<pair<int, int>> candidates;
void add(int i, int j) {
    if (i >= n || j >= n) return;
    candidates.insert({i, j}); //ВАЖНО, чтобы код сравнивал не пары i, j а дроби a[i]/b[j]
}

...

candidates.insert({0, 0});
for (int i = 0; i < k; ++i) {
    auto [x, y] = *candidates.begin();
    candidates.erase(candidates.begin());
    add(x + 1, y);
    add(x, y + 1);
auto [x, y] = *candidates.begin();
int g = __gcd(a[x], b[y]);
x = a[x] / g;
y = b[y] / g;
cout << x << '/' << y;

Можно представить взвешенный ориентированный граф на $$$n^2$$$ вершин где ребро $$$(i, j) \rightarrow (k, l)$$$ существует если $$$(i, j) \leq (k, l)$$$, а вес ребра $$$w= (k, l) - (i, j)$$$. Тогда если на данном графе запустить дейкстру, то он обойдет дроби в отсортированном порядке. Тогда переход из вершины $$$(i, j)$$$ в вершину $$$(i+ 1, j)$$$ будет не хуже любого перехода из вершины $$$(i, j)$$$ в вершину $$$(i+ k, j), 0 < k$$$

Каждый раз, когда мы получаем i-ый элемент в отсортированном массиве, мы удаляем из кандидатов 1 элемент и добавляем не более 2х новых. Получаем, что время работы $$$O(k*logk)$$$

Каждый раз, когда мы получаем, что оптимальная пара является плохой, мы удаляем из кандидатов 1 элемент и добавляем не более 2х новых. Так как каждая плохая пара может встретиться только в одной паре $$$(cnt_x, cnt_y)$$$, каждую плохую пару мы обработаем не более одного раза. Получаем, что время работы $$$O(m * logn + n)$$$

The milk tea in China is very delicious. There are many binary ("either-or") options for customizing a milk tea order, such as:

"with ice" OR "no ice" "with sugar" OR "no sugar" "with bubbles" OR "no bubbles" "with pudding" OR "no pudding" and so on. A customer's preferences for their milk tea can be represented as a binary string. For example, using the four properties above (in the order they are given), the string 1100 means "with ice, with sugar, no bubbles, no pudding".

Today, Shakti is on duty to buy each of his N friends a milk tea, at a shop that offers P binary options. But after collecting everyone's preferences, Shakti found that the order was getting too complicated, so Shakti has decided to buy the same type of milk tea for everyone. Shakti knows that for every friend, for every preference that is not satisfied, they will complain once. For example, if two of the friends have preferences for types 101 and 010, and Shakti chooses type 001, then the first friend will complain once and the second friend will complain twice, for a total of three complaints.

Moreover, there are M different forbidden types of milk tea that the shop will not make, and Shakti cannot choose any of those forbidden types.

What is the smallest number of complaints that Shakti can get? $$$1 \leq N \leq 100, 1 \leq P \leq 100, 0 \leq M \leq min(100, 2^P - 1)$$$.

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef long double ld;

/*
⣿⣿⣷⡁⢆⠈⠕⢕⢂⢕⢂⢕⢂⢔⢂⢕⢄⠂⣂⠂⠆⢂⢕⢂⢕⢂⢕⢂⢕⢂
⣿⣿⣿⡷⠊⡢⡹⣦⡑⢂⢕⢂⢕⢂⢕⢂⠕⠔⠌⠝⠛⠶⠶⢶⣦⣄⢂⢕⢂⢕
⣿⣿⠏⣠⣾⣦⡐⢌⢿⣷⣦⣅⡑⠕⠡⠐⢿⠿⣛⠟⠛⠛⠛⠛⠡⢷⡈⢂⢕⢂
⠟⣡⣾⣿⣿⣿⣿⣦⣑⠝⢿⣿⣿⣿⣿⣿⡵⢁⣤⣶⣶⣿⢿⢿⢿⡟⢻⣤⢑⢂
⣾⣿⣿⡿⢟⣛⣻⣿⣿⣿⣦⣬⣙⣻⣿⣿⣷⣿⣿⢟⢝⢕⢕⢕⢕⢽⣿⣿⣷⣔
⣿⣿⠵⠚⠉⢀⣀⣀⣈⣿⣿⣿⣿⣿⣿⣿⣿⣿⣗⢕⢕⢕⢕⢕⢕⣽⣿⣿⣿⣿
⢷⣂⣠⣴⣾⡿⡿⡻⡻⣿⣿⣴⣿⣿⣿⣿⣿⣿⣷⣵⣵⣵⣷⣿⣿⣿⣿⣿⣿⡿
⢌⠻⣿⡿⡫⡪⡪⡪⡪⣺⣿⣿⣿⣿⣿⠿⠿⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠃
⠣⡁⠹⡪⡪⡪⡪⣪⣾⣿⣿⣿⣿⠋⠐⢉⢍⢄⢌⠻⣿⣿⣿⣿⣿⣿⣿⣿⠏⠈
⡣⡘⢄⠙⣾⣾⣾⣿⣿⣿⣿⣿⣿⡀⢐⢕⢕⢕⢕⢕⡘⣿⣿⣿⣿⣿⣿⠏⠠⠈
⠌⢊⢂⢣⠹⣿⣿⣿⣿⣿⣿⣿⣿⣧⢐⢕⢕⢕⢕⢕⢅⣿⣿⣿⣿⡿⢋⢜⠠⠈
⠄⠁⠕⢝⡢⠈⠻⣿⣿⣿⣿⣿⣿⣿⣷⣕⣑⣑⣑⣵⣿⣿⣿⡿⢋⢔⢕⣿⠠⠈
⠨⡂⡀⢑⢕⡅⠂⠄⠉⠛⠻⠿⢿⣿⣿⣿⣿⣿⣿⣿⣿⡿⢋⢔⢕⢕⣿⣿⠠⠈
⠄⠪⣂⠁⢕⠆⠄⠂⠄⠁⡀⠂⡀⠄⢈⠉⢍⢛⢛⢛⢋⢔⢕⢕⢕⣽⣿⣿⠠⠈
*/
#define all(a) a.begin(), a.end()
#define FNAME ""
#define int ll
typedef pair<int, int> pii;
#define _ << ' ' <<
#define vec vector
const bool DEBUG = true;

#ifndef HOME
#define err \
    if (0) cerr
#else
#define err \
    if (DEBUG) cerr
#endif

#ifdef int
const int INF = 2e16;
#else
const int INF = 2e9;
#endif
mt19937 gen(time(0));
//END

set<pii> st;
const int MAXN = 1e5;
vec<int> t[MAXN];
int lst = 0;
vec<int> cnt;
int n;
void add(vec<int> &v) {
    t[lst] = v;
    int tmp = 0;
    int sz = v.size();
    for (int i = 0; i < sz; ++i) {
        if (v[i]) {
            tmp += n - cnt[i];
        } else {
            tmp += cnt[i];
        }
    }
    st.insert({tmp, lst});
    lst++;
}
void solve() {
    //code here
    
    int m, p;
    cin >> n >> m >> p;
    
    cnt.assign(p, 0);
    lst = 0;
    st.clear();


    for (int i = 0; i < n; ++i) {
        string s;
        cin >> s;
        for (int j = 0; j < p; ++j) {
            int x = s[j] - '0';
            cnt[j] += x;
        }
    }
    set<vec<int>> usd;
    for (int i = 0; i < m; ++i) {
        vec<int> v(p);
        for (int j = 0; j < p; ++j) {
            char x;
            cin >> x;
            if (x == '1') v[j] = 1;
        }
        usd.insert(v);
    }
    vec<int> init(p);
    for (int i = 0; i < p; ++i) {
        if (cnt[i] > n - cnt[i]) {
            init[i] = 1;
        }
    }
    add(init);
    set<vec<int>> myusd;
    while (!st.empty()) {
        auto [x, i] = *st.begin();
        st.erase(st.begin());
        vec<int> v = t[i];
        if (usd.count(v) == 0) {
            cout << x;
            return;
        }
        myusd.insert(v);
        for (int i = 0; i < p; ++i) {
            v[i] ^= 1;
            if (myusd.count(v) == 0) {
    
                add(v);
            }
            v[i] ^= 1;
        }
    }
//    assert(0);


    //
}

signed main() {
#ifdef HOME
    freopen("input.txt", "r", stdin);
    //freopen("input.txt", "w", stdout);
#else
    if (FNAME != "") {
        freopen(FNAME ".in", "r", stdin);
        freopen(FNAME ".out", "w", stdout);
    }
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int tt = 1;
        cin >> tt;
    for (int req = 0; req < tt; ++req) {
        unsigned start = clock();
        cout << "Case #" << req + 1 << ": ";
        solve();
        cout << '\n';
        unsigned end = clock();
        cerr << "WorkTime: " << (end - start) / (double) CLOCKS_PER_SEC << '\n';
    }
}

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define int ll
typedef pair<int, int> pii;
#define vec vector
//END

class SegTree {
    int n;
    vec<pii> t;
    vec<int> p;
    vec<int> a;
    pii mrg(pii a, pii b) {
        return {a.first + b.first, a.second + b.second};
    }
    void build(int v, int l, int r) {
        if (l == r - 1) {
            if (a[l]) {
                t[v] = {1, 0};
            } else {
                t[v] = {0, 1};
            }
            return;
        }
        int m = (r + l) / 2;
        build(2 * v + 1, l, m);
        build(2 * v + 2, m, r);
        t[v] = mrg(t[2 * v + 1], t[2 * v + 2]);
    }
    void push(int v, int l, int r) {
        if (p[v]) {
            swap(t[v].second, t[v].first);
        }
        if (l != r - 1) {
            p[2 * v + 1] ^= p[v];
            p[2 * v + 2] ^= p[v];
        }
        p[v] = 0;
    }
    void upd(int v, int l, int r, int L, int R) {
        if (L <= l && r <= R) {
            p[v] ^= 1;
            push(v, l, r);
            return;
        }
        push(v, l, r);
        if (R <= l || r <= L) {
            return;
        }
        int m = (r + l) / 2;
        upd(2 * v + 1, l, m, L, R);
        upd(2 * v + 2, m, r, L, R);
        t[v] = mrg(t[2 * v + 1], t[2 * v + 2]);
    }
    int get(int v, int l, int r, int L, int R) {
        push(v, l, r);
        if (L <= l && r <= R) {
            return t[v].first;
        }
        if (R <= l || r <= L) {
            return 0;
        }
        int m = (r + l) / 2;
        int a = get(2 * v + 1, l, m, L, R);
        int b = get(2 * v + 2, m, r, L, R);
        return a + b;
    }

public:
    SegTree(vec<int> &a) : a(a) {
        n = a.size();
        t.resize(4 * n);
        p.resize(4 * n);
        if (n) {
            build(0, 0, n);
        }
    }
    int get(int l, int r) {
        if (n == 0) return 0;
        return get(0, 0, n, l, r);
    }
    void upd(int l, int r) {
        if (n == 0) return;
        upd(0, 0, n, l, r);
    }
    
};

void solve() {
    //code here
    int n, m;
    cin >> n >> m;
    vec<int> a, b;
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        if (i % 2) {
            b.push_back(x);
        } else {
            a.push_back(x);
        }
    }
    SegTree sga(a), sgb(b);
    for (int i = 0; i < m; ++i) {
        int t, l, r;
        cin >> t >> l >> r;
        l--;
        r--;
        int l1, r1, l2, r2;
        l1 = (l + 1) / 2;
        r1 = r / 2;
        r2 = (r - 1) / 2;
        if (l % 2) {
            l2 = (l) / 2;
            
        } else {
            l2 = (l + 1) / 2;
        }
        if (t == 1) {
            if (l % 2) {
                sgb.upd(l2, r2 + 1);
            } else {
                sga.upd(l1, r1 + 1);
            }
        } else {
            int cnt = sga.get(l1, r1 + 1) + sgb.get(l2, r2 + 1);
            cout << cnt << '\n';
        }
    }
    //
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int tt = 1;
    //    cin >> tt;
    for (int req = 0; req < tt; ++req) {
        unsigned start = clock();
        solve();
        cout << '\n';
        unsigned end = clock();
        cerr << "WorkTime: " << (end - start) / (double) CLOCKS_PER_SEC << '\n';
    }
}

В данной задаче несложно заметить что у нас применяется xor на отрезке(возможно пустом) четных и нечетных индексов.Для решения можно разбить исходный массив на два с элементами на четных(a) и нечетных(b) индексах. Так мы свели задачу к xor на отрезке, количество 1 на отрезке.