Посчитайте для каждой семьи две величины: сколько её представителей в очереди и на какой позиции стоит самый первый.

Сортировка семей двухуровневая: сначала по количеству (по убыванию), при равенстве — по позиции первого представителя (по возрастанию).

Попробуйте завести два массива: amount[x] — число людей из семьи x и firstTime[x] — минимальный индекс, на котором встречается семья x. Пройдите по входу один раз и заполните оба. Затем сложите все уникальные номера семей в вектор и отсортируйте их компаратором:

if (amount[a] != amount[b]) return amount[a] > amount[b];
return firstTime[a] < firstTime[b];

Осталось вывести каждую семью столько раз, сколько у неё людей. Сложность — O(n log n).

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<int> people(n);
    vector<int> amount(m + 1, 0), firstTime(m + 1, -1);
    for (int i = 0; i < n; i++) {
        cin >> people[i];
        amount[people[i]]++;
        if (firstTime[people[i]] == -1) {
            firstTime[people[i]] = i;
        }
    }
    vector<int> uniqueFamilies;
    for (int x = 1; x <= m; x++) {
        if (amount[x] > 0) {
            uniqueFamilies.push_back(x);
        }
    }
    sort(uniqueFamilies.begin(), uniqueFamilies.end(),
         [&](int a, int b) {
             if (amount[a] != amount[b]) {
                 return amount[a] > amount[b];
             }
             return firstTime[a] < firstTime[b];
         });
    for (int fam : uniqueFamilies) {
        for (int k = 0; k < amount[fam]; k++) {
            cout << fam << ' ';
        }
    }
    cout << '\n';
    return 0;
}

Это обычный пузырёк с оптимизацией: после каждого прохода правая часть массива уже отсортирована.

Границей следующего прохода служит индекс последнего обмена в текущем проходе. Если обменов не было — сортировка завершена.

Промоделируйте процесс. Пусть limit — количество пар для просмотра в текущем проходе. Изначально limit = n - 1. На каждом проходе пробегайте i от 0 до limit - 1, увеличивайте счётчик секунд, при необходимости меняйте местами a[i] и a[i+1] и запоминайте lastSwap = i. После прохода, если lastSwap == -1, выходите. Иначе limit = lastSwap.

Сложность — O(n²) в худшем случае, но при n ≤ 1000 этого достаточно.

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    long long totalSeconds = 0;
    int limit = n - 1;
    while (limit > 0) {
        int lastSwap = -1;
        for (int i = 0; i < limit; i++) {
            totalSeconds++;
            if (a[i] > a[i + 1]) {
                swap(a[i], a[i + 1]);
                lastSwap = i;
            }
        }
        if (lastSwap == -1) {
            break;
        }
        limit = lastSwap;
    }
    cout << totalSeconds << '\n';
    return 0;
}

Алфавит — линейная цепочка: у каждой буквы максимум один «следующий» и максимум один «предыдущий».

Проверьте три вещи: нет развилок, нет слияний, обход от начала цепочки покрывает все встречающиеся буквы и не натыкается на цикл.

Постройте ориентированный граф на 26 буквах. Для каждой пары (X, Y) проверьте: у X ещё нет исходящего ребра в другую букву; у Y ещё нет входящего ребра из другой буквы. Иначе — NO. После добавления всех рёбер найдите единственную букву с in-degree = 0 и пройдите по цепочке, помечая посещённые. Если наткнулись на уже посещённую букву — цикл. Если длина обхода меньше общего числа встречающихся букв — потерялась компонента. В обоих случаях NO.

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> nextLetter(26, -1), prevLetter(26, -1);
    vector<int> appears(26, 0);
    for (int i = 0; i < n; i++) {
        char x, y;
        cin >> x >> y;
        int a = x - 'A', b = y - 'A';
        appears[a] = appears[b] = 1;
        if (nextLetter[a] != -1 && nextLetter[a] != b) {
            cout << "NO\n";
            return 0;
        }
        if (prevLetter[b] != -1 && prevLetter[b] != a) {
            cout << "NO\n";
            return 0;
        }
        nextLetter[a] = b;
        prevLetter[b] = a;
    }
    int start = -1;
    for (int i = 0; i < 26; i++) {
        if (appears[i] && prevLetter[i] == -1) {
            if (start != -1) {
                cout << "NO\n";
                return 0;
            }
            start = i;
        }
    }
    if (start == -1) {
        cout << "NO\n";
        return 0;
    }
    vector<int> visited(26, 0);
    string result;
    int cur = start;
    while (cur != -1) {
        if (visited[cur]) {
            cout << "NO\n";
            return 0;
        }
        visited[cur] = 1;
        result += char('A' + cur);
        cur = nextLetter[cur];
    }
    int totalUsed = 0;
    for (int i = 0; i < 26; i++) {
        totalUsed += appears[i];
    }
    if ((int)result.size() != totalUsed) {
        cout << "NO\n";
        return 0;
    }
    cout << result << '\n';
    return 0;
}

Рассмотрите задачу как DP по префиксу: best[i] — лучший ответ для первых i кейсов.

Если открыть i-й кейс, следующие m пропускаются. Переход: best[i] = max(best[i-1], value[i] + best[i-m-1]).

Классическая задача о «взять или пропустить с блокировкой». Попробуйте вести best[i] — максимальная сумма на префиксе длины i. Для каждого i: либо не берём i-й кейс (best[i-1]), либо берём его и перескакиваем m следующих (value[i] + best[max(0, i-m-1)]). Ответ — best[n]. Значения сумм могут достигать 10^14, нужен long long.

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<long long> value(n + 1, 0), best(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        cin >> value[i];
    }
    for (int i = 1; i <= n; i++) {
        int jumpBack = i - m - 1;
        if (jumpBack < 0) {
            jumpBack = 0;
        }
        best[i] = max(best[i - 1], value[i] + best[jumpBack]);
    }
    cout << best[n] << '\n';
    return 0;
}

В задаче n · m ≤ 10^5, значит можно спокойно пройтись по всей матрице один раз.

Для каждой высоты запомните ячейку с минимальным номером столбца, а при равенстве — с минимальным номером ряда.

Пройдитесь по матрице и попробуйте завести map<int, pair<int,int>>, где ключ — высота, а значение — координаты (row, col). При встрече новой высоты записывайте её. При повторной — сравнивайте: если новая ячейка лучше по столбцу, или равна по столбцу и лучше по строке, обновляйте. На запросы отвечайте за O(log n) через map.

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, q;
    cin >> n >> m >> q;
    map<int, pair<int,int>> bestCell;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            int h;
            cin >> h;
            auto it = bestCell.find(h);
            if (it == bestCell.end()) {
                bestCell[h] = {i, j};
            } else {
                auto [row, col] = it->second;
                if (j < col || (j == col && i < row)) {
                    it->second = {i, j};
                }
            }
        }
    }
    while (q--) {
        int h;
        cin >> h;
        auto it = bestCell.find(h);
        if (it == bestCell.end()) {
            cout << -1 << '\n';
        } else {
            cout << it->second.first << ' '
                 << it->second.second << '\n';
        }
    }
    return 0;
}

Поддерживайте переменную leftBorder — минимальный номер уже разрушенной секции. Берляндия работает на [1, leftBorder-1], Флатландия — на [leftBorder+1, n].

При равенстве прочностей Берляндия выбирает самую правую секцию, Флатландия — самую левую. Храните в дереве отрезков пару (значение, индекс).

Попробуйте завести два дерева отрезков: treeBerland для Берляндии с правилом «при равенстве — правый индекс», treeFlatland для Флатландии — «при равенстве — левый». Оба стройте по массиву strength. Секцию m сразу помечайте INF. Переменная leftBorder = m. На каждый ход: если B, запрашивайте минимум на [1, leftBorder-1] в treeBerland; если F, запрашивайте минимум на [leftBorder+1, n] в treeFlatland. Полученный индекс выводите, помечайте INF в обоих деревьях, обновляйте leftBorder = min(leftBorder, idx). Сложность — O((n + q) log n).

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

const int INF = 2e9 + 7;

struct SegTree {
    int n;
    vector<pair<int,int>> tree;
    bool preferRight;
    SegTree(int sz, bool pr) : n(sz), preferRight(pr) {
        tree.resize(4 * sz + 4);
    }
    pair<int,int> combine(pair<int,int> a, pair<int,int> b) {
        if (a.first < b.first) return a;
        if (b.first < a.first) return b;
        if (preferRight) {
            return {a.first, max(a.second, b.second)};
        }
        return {a.first, min(a.second, b.second)};
    }
    void build(int v, int l, int r, const vector<int>& strength) {
        if (l == r) {
            tree[v] = {strength[l], l};
            return;
        }
        int mid = (l + r) / 2;
        build(2*v, l, mid, strength);
        build(2*v+1, mid+1, r, strength);
        tree[v] = combine(tree[2*v], tree[2*v+1]);
    }
    void update(int v, int l, int r, int pos) {
        if (l == r) {
            tree[v] = {INF, l};
            return;
        }
        int mid = (l + r) / 2;
        if (pos <= mid) {
            update(2*v, l, mid, pos);
        } else {
            update(2*v+1, mid+1, r, pos);
        }
        tree[v] = combine(tree[2*v], tree[2*v+1]);
    }
    pair<int,int> query(int v, int l, int r, int ql, int qr) {
        if (ql > r || qr < l) return {INF, -1};
        if (ql <= l && r <= qr) return tree[v];
        int mid = (l + r) / 2;
        pair<int,int> leftPart = query(2*v, l, mid, ql, qr);
        pair<int,int> rightPart = query(2*v+1, mid+1, r, ql, qr);
        return combine(leftPart, rightPart);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<int> strength(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> strength[i];
    }
    string order;
    cin >> order;
    SegTree treeBerland(n, true), treeFlatland(n, false);
    treeBerland.build(1, 1, n, strength);
    treeFlatland.build(1, 1, n, strength);
    treeBerland.update(1, 1, n, m);
    treeFlatland.update(1, 1, n, m);
    int leftBorder = m;
    for (char c : order) {
        int idx;
        if (c == 'B') {
            idx = treeBerland.query(1, 1, n, 1, leftBorder - 1).second;
        } else {
            idx = treeFlatland.query(1, 1, n, leftBorder + 1, n).second;
        }
        cout << idx << ' ';
        treeBerland.update(1, 1, n, idx);
        treeFlatland.update(1, 1, n, idx);
        leftBorder = min(leftBorder, idx);
    }
    cout << '\n';
    return 0;
}

Все пары взаимно просты тогда и только тогда, когда ни одно простое число не делит одновременно два видимых числа.

Попробуйте завести divCount[p] — сколько активных чисел делятся на p, и переменную conflicts — сколько простых имеют divCount[p] ≥ 2. Ответ растёт, когда conflicts == 0.

Линейным решетом считайте наименьший простой делитель spf[] для всех чисел до 10^7. Для запроса x получайте список его простых делителей. При +x увеличивайте divCount[p] для каждого делителя. Если divCount[p] стало равно 2, увеличивайте conflicts. При -x уменьшайте divCount[p]. Если divCount[p] стало равно 1, уменьшайте conflicts. После обработки каждой команды, если conflicts == 0, добавляйте 1 к ответу. Сложность — O(MAX + q · log MAX), где MAX = 10^7.

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

const int MAXV = 10000000;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    vector<int> spf(MAXV + 1, 0);
    vector<int> primes;
    for (int i = 2; i <= MAXV; i++) {
        if (spf[i] == 0) {
            spf[i] = i;
            primes.push_back(i);
        }
        for (int p : primes) {
            if (p > spf[i] || (long long)i * p > MAXV) {
                break;
            }
            spf[i * p] = p;
        }
    }
    int q;
    cin >> q;
    vector<int> divCount(MAXV + 1, 0);
    int conflicts = 0, goodMoments = 0;
    while (q--) {
        string op;
        cin >> op;
        char sign = op[0];
        int value = stoi(op.substr(1));
        vector<int> primeFactors;
        while (value > 1) {
            int p = spf[value];
            primeFactors.push_back(p);
            while (value % p == 0) {
                value /= p;
            }
        }
        if (sign == '+') {
            for (int p : primeFactors) {
                divCount[p]++;
                if (divCount[p] == 2) {
                    conflicts++;
                }
            }
        } else {
            for (int p : primeFactors) {
                divCount[p]--;
                if (divCount[p] == 1) {
                    conflicts--;
                }
            }
        }
        if (conflicts == 0) {
            goodMoments++;
        }
    }
    cout << goodMoments << '\n';
    return 0;
}