Намёк: не надо решать, удалять ( или ) по их общему количеству. Важно не сколько всего скобок каждого типа, а какие из них образуют покрытие всех возможных пар ( перед ).

Текущий код ломается, например, на:

text
1
6 1
))((()

Оптимально удалить последнюю ), тогда стоимость станет 0.

А твой код при ko <= kz удалит первую (, получится:

text
))(() 

и там всё ещё есть подпоследовательность "()", то есть стоимость 2.

---

Идея минимальной правки

Стоимость строки — это:

text
2 * количество пар, которые можно сопоставить

Пару можно сделать, если есть ( слева и ) справа.

Рассмотрим некоторую границу split.

Возьмём множество:

text
все '(' слева от границы
+
все ')' справа от границы

Такое множество пересекает любую возможную пару ( ... ).
Если удалить все эти символы, пар точно не останется.

Нам надо найти границу, где это множество минимально.

Для границы после позиции i размер множества равен:

text
количество '(' в префиксе + количество ')' в суффиксе

Это можно переписать как:

text
total_close + balance

где:

cpp
balance = открывающие_в_префиксе - закрывающие_в_префиксе

Значит надо найти позицию, где balance минимален.

---

Минимально исправленный код

Я оставил структуру твоего кода почти такой же: чтение, ans, вывод. Заменена только неправильная логика выбора удаляемых символов.

cpp
#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int t;
    cin >> t;

    while (t--) {
        int n, k;
        cin >> n >> k;

        string s;
        cin >> s;

        int ko = 0, kz = 0;
        for (int i = 0; i < n; ++i) {
            if (s[i] == '(') ko++;
            else kz++;
        }

        vector<int> ans(n);

        int b = 0;
        int mn = 0;
        int split = -1;

        for (int i = 0; i < n; ++i) {
            if (s[i] == '(') b++;
            else b--;

            if (b < mn) {
                mn = b;
                split = i;
            }
        }

        for (int i = 0; i < n && k > 0; ++i) {
            if (i <= split && s[i] == '(') {
                ans[i] = 1;
                k--;
            } else if (i > split && s[i] == ')') {
                ans[i] = 1;
                k--;
            }
        }

        for (auto u : ans) cout << u;
        cout << '\n';
    }

    return 0;
}

---

Что именно изменилось

Вместо этого блока:

cpp
if (ko <= kz && k != 0) {
    ...
} else if (k != 0) {
    ...
}

мы теперь делаем так:

cpp
int b = 0;
int mn = 0;
int split = -1;

for (int i = 0; i < n; ++i) {
    if (s[i] == '(') b++;
    else b--;

    if (b < mn) {
        mn = b;
        split = i;
    }
}

Здесь split — позиция, после которой выгодно провести границу.

Потом удаляем символы из множества:

cpp
i <= split && s[i] == '('

или

cpp
i > split && s[i] == ')'

То есть:

text
'(' слева от границы
')' справа от границы

---

Почему этого достаточно

Любая правильная пара имеет вид:

text
'(' раньше, ')' позже

Если ( стоит слева от split, мы можем покрыть пару удалением этой (.

Если ( стоит справа от split, то соответствующая ) тоже обязательно справа от split, значит пару можно покрыть удалением этой ).

То есть выбранное множество символов пересекает каждую возможную пару.

Если удалить один символ из такого множества, максимальное число пар уменьшится ровно на 1, пока пары ещё есть. Поэтому можно просто удалить первые k подходящих символов.

Если k больше, чем нужно, удалятся не все k, а только полезные символы. Это разрешено, потому что по условию надо удалить не более k символов.

Главная ошибка: ты хранишь все u и v:

cpp
vector<int> u(m + 1), v(m + 1);

А m до 10^7.

Это примерно:

text
u: 40 МБ
v: 40 МБ

Уже 80 МБ, а лимит — 64 МБ. Поэтому будет превышение памяти.

Нужно хранить только текущие u, v, потому что каждый следующий запрос зависит только от предыдущего.

Ещё лучше заменить long long в таблице на int, потому что элементы массива меньше 16714589.

---

Минимально исправленный код:

cpp
#include <iostream>
#include <vector>
using namespace std;

const int mod = 16714589;
vector<int> a, logs;
vector<vector<int>> table;

int get(int l, int r) {
    int len = r - l + 1;
    int k = logs[len];

    return min(table[k][l], table[k][r - (1 << k) + 1]);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, m, a1;
    cin >> n >> m >> a1;

    a.resize(n);
    a[0] = a1;
    for (int i = 1; i < n; ++i) {
        a[i] = (1LL * a[i - 1] * 23 + 21563) % mod;
    }

    logs.resize(n + 1);
    logs[1] = 0;
    for (int i = 2; i <= n; ++i) {
        logs[i] = logs[i / 2] + 1;
    }

    int lg = logs[n];
    table.resize(lg + 1, vector<int>(n));

    for (int i = 0; i < n; ++i) table[0][i] = a[i];

    for (int k = 1; k <= lg; ++k) {
        for (int j = 0; j <= n - (1 << k); ++j) {
            table[k][j] = min(table[k - 1][j], table[k - 1][j + (1 << (k - 1))]);
        }
    }

    int u, v;
    cin >> u >> v;

    int ans = 0;

    for (int i = 1; i <= m; ++i) {
        int l = min(u, v) - 1;
        int r = max(u, v) - 1;

        ans = get(l, r);

        if (i == m) {
            cout << u << ' ' << v << ' ' << ans;
            break;
        }

        int nu = ((17LL * u + 751 + ans + 2LL * i) % n) + 1;
        int nv = ((13LL * v + 593 + ans + 5LL * i) % n) + 1;

        u = nu;
        v = nv;
    }

    return 0;
}

Что изменилось минимально:

cpp
vector<long long> a, logs;
vector<vector<long long>> table;

заменили на:

cpp
vector<int> a, logs;
vector<vector<int>> table;

Потому что значения маленькие, long long не нужен.

Было:

cpp
vector<int> u(m + 1), v(m + 1);

Стало:

cpp
int u, v;

Потому что нам не нужны все запросы, нужен только текущий.

Цикл стал таким:

cpp
for (int i = 1; i <= m; ++i)

Потому что формулы используют номер запроса i, начиная с 1.

И важно: сначала считаем ответ на текущий запрос, потом, если это не последний запрос, генерируем следующий.

Разберу обе задачи.

---

1. D. Совершенно новое татарское телешоу

Главная ошибка

Твой код пытается делить значения на группы и смотреть только:

cpp
m[m1] % 2

и наличие второго элемента в группе.

Но игра устроена не так. Важно не просто количество максимального элемента, а есть ли дальше проигрышная позиция, в которую можно сходить.

Ещё в твоём коде есть техническая ошибка:

cpp
int pr = -1;
for (auto u : s) {
    if (pr == -1 || pr - u > k) {
        ...
    }
}

Ты нигде не делаешь:

cpp
pr = u;

То есть pr всегда остаётся -1, и группировка вообще не работает.

---

Правильная идея

Пусть есть некоторое значение x.

После того как Арсений выбрал x, следующий ход делает Егор.

Егор может брать:

text
y >= x и y - x <= k

То есть игра всегда идёт вправо по значениям, назад вернуться нельзя.

Для каждого различного значения x посчитаем:

cpp
lose[x]

Это значит: если предыдущим ходом уже взяли x, и сейчас ход текущего игрока, то текущий игрок проигрывает.

Если количество x нечётное, то после первого взятия x остаётся чётное число таких же x.

Если из x нельзя перейти в уже проигрышную позицию, то позиция проигрышная.

Формула такая:

cpp
lose[i] = cnt[i] % 2 == 1 && нет проигрышного значения справа на расстоянии <= k

Почему cnt[i] % 2 == 1?

Потому что Арсений уже взял один элемент x.

Осталось:

cpp
cnt[x] - 1

Если cnt[x] нечётное, то cnt[x] - 1 чётное. Тогда игра на одинаковых x сама по себе проигрышная, если нет хорошего перехода вправо.

---

Минимально исправленный код

Я оставил твои set, map, vector, но полностью заменил неправильную логику группировки.

cpp
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int t;
    cin >> t;

    while (t--) {
        int n, k;
        cin >> n >> k;

        set<int> d;
        vector<int> a(n);
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
            d.insert(a[i]);
        }

        map<int, int> m;
        for (int i = 0; i < n; ++i) {
            m[a[i]]++;
        }

        vector<int> s;
        for (auto u : d) s.push_back(u);

        set<int> lose_values;
        bool fl = false;

        for (int i = (int)s.size() - 1; i >= 0; --i) {
            int x = s[i];

            auto it = lose_values.upper_bound(x);

            bool has_lose = false;
            if (it != lose_values.end() && *it - x <= k) {
                has_lose = true;
            }

            bool lose = (m[x] % 2 == 1 && !has_lose);

            if (!lose) {
                fl = true;
            } else {
                lose_values.insert(x);
            }
        }

        if (fl) cout << "YES\n";
        else cout << "NO\n";
    }

    return 0;
}

---

Что изменилось

Было:

cpp
vector<pair<int, int>> v(n);
int id = 0;
int pr = -1;
...

Это удалено, потому что такая группировка не описывает игру.

Добавили:

cpp
set<int> lose_values;

Тут храним значения, из которых следующий игрок проигрывает.

Проверяем, есть ли проигрышное значение справа:

cpp
auto it = lose_values.upper_bound(x);

bool has_lose = false;
if (it != lose_values.end() && *it - x <= k) {
    has_lose = true;
}

Если есть проигрышное значение справа на расстоянии <= k, значит текущая позиция выигрышная: можно сходить туда.

Считаем:

cpp
bool lose = (m[x] % 2 == 1 && !has_lose);

Если позиция не проигрышная, значит Арсений может выбрать это значение, и Егор будет выигрывать:

cpp
if (!lose) {
    fl = true;
}

---

2. C. Омские программисты

Главная ошибка

Твой код жадный:

cpp
if (r1 < r2) {
    ans += 2;
    b /= x;
    a /= x;
} else {
    ans++;
    b /= x;
}

Но локально лучший ход не всегда ведёт к глобальному минимуму.

Тут надо перебрать, сколько раз мы делим a, и сколько раз делим b.

После этого меньшее число можно догнать операциями +1.

То есть вариант такой:

text
поделили a i раз
поделили b j раз
потом прибавили разницу

Цена:

cpp
i + j + abs(a_after - b_after)

Так как a, b <= 1e9, делений будет мало: максимум около 31 при x = 2.

---

Минимально исправленный код

cpp
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int t;
    cin >> t;

    while (t--) {
        long long a, b, x;
        cin >> a >> b >> x;

        vector<long long> va, vb;

        long long cur = a;
        while (true) {
            va.push_back(cur);
            if (cur == 0) break;
            cur /= x;
        }

        cur = b;
        while (true) {
            vb.push_back(cur);
            if (cur == 0) break;
            cur /= x;
        }

        long long ans = abs(a - b);

        for (int i = 0; i < (int)va.size(); ++i) {
            for (int j = 0; j < (int)vb.size(); ++j) {
                ans = min(ans, 1LL * i + j + abs(va[i] - vb[j]));
            }
        }

        cout << ans << '\n';
    }

    return 0;
}

---

Что здесь происходит

Например, для числа a строим все варианты после делений:

cpp
vector<long long> va;

long long cur = a;
while (true) {
    va.push_back(cur);
    if (cur == 0) break;
    cur /= x;
}

То есть если:

text
a = 20, x = 3

то получим:

text
20, 6, 2, 0

Индексы в этом массиве — это количество операций деления.

Например:

cpp
va[2] = 2

значит:

text
20 / 3 / 3 = 2

и это стоит 2 операции.

Потом перебираем:

cpp
for (int i = 0; i < va.size(); ++i) {
    for (int j = 0; j < vb.size(); ++j) {
        ans = min(ans, i + j + abs(va[i] - vb[j]));
    }
}

Смысл:

text
i делений сделали с a
j делений сделали с b
потом меньшее число увеличили до большего

Количество +1 операций равно:

cpp
abs(va[i] - vb[j])

Итого:

cpp
i + j + abs(va[i] - vb[j])

---

Почему это быстро

Даже если a = 1e9, а x = 2, цепочка делений короткая:

text
1e9, 5e8, 2.5e8, ..., 0

Это примерно 31 значение.

Значит на один тест:

text
31 * 31

операций, что очень мало.