For each family, compute two values: how many of its members are in the queue, and the position of the earliest one.

The sorting of families is two-level: first by count (descending), and on ties — by the position of the earliest member (ascending).

Try to maintain two arrays: amount[x] — the number of people from family x, and firstTime[x] — the smallest index at which family x appears. Go through the input once and fill in both. Then collect all distinct family IDs into a vector and sort them with the comparator:

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

All that's left is to print each family as many times as it has people. Complexity — 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;
}

This is the ordinary bubble sort with an optimization: after each pass, the right part of the array is already sorted.

The bound of the next pass is the index of the last swap in the current pass. If there were no swaps — the sorting is done.

Simulate the process. Let limit be the number of pairs to consider in the current pass. Initially limit = n - 1. On each pass, iterate i from 0 to limit - 1, increment the seconds counter, and if needed swap a[i] and a[i+1], remembering lastSwap = i. After the pass, if lastSwap == -1, stop. Otherwise limit = lastSwap.

Complexity — O(n²) in the worst case, but with n ≤ 1000 this is more than enough.

#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;
}

The alphabet is a linear chain: each letter has at most one "next" and at most one "previous".

Check three things: no forks, no merges, and the traversal from the start of the chain covers every letter that appears and doesn't run into a cycle.

Build a directed graph on 26 letters. For each pair (X, Y), check: X doesn't already have an outgoing edge to another letter; Y doesn't already have an incoming edge from another letter. Otherwise — NO. After adding all edges, find the only letter with in-degree = 0 and walk along the chain, marking visited letters. If you hit a visited letter — a cycle. If the traversal length is less than the total number of letters that appear — a component is missing. In both cases, 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;
}

Treat the problem as a prefix DP: best[i] — the best answer for the first i cases.

If you open case i, the next m are skipped. Transition: best[i] = max(best[i-1], value[i] + best[i-m-1]).

This is the classic "take or skip with a cooldown" problem. Try to maintain best[i] — the maximum total value on a prefix of length i. For each i: either skip case i (best[i-1]), or take it and jump over m following (value[i] + best[max(0, i-m-1)]). The answer is best[n]. The sums can reach 10^14, so long long is required.

#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;
}

In this problem n · m ≤ 10^5, so you can safely traverse the entire matrix once.

For each height, remember the cell with the smallest column index, and on ties — the smallest row index.

Walk through the matrix and try to maintain map<int, pair<int,int>> where the key is the height and the value is the coordinates (row, col). When you see a new height, record it. When you see it again — compare: if the new cell is better by column, or equal by column and better by row, update. Queries are answered in O(log n) via 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;
}

Maintain a variable leftBorder — the smallest index among destroyed sections. Berlandia works on [1, leftBorder-1], Flatlandia works on [leftBorder+1, n].

On ties in strength, Berlandia picks the rightmost section, Flatlandia picks the leftmost. Store a pair (value, index) in the segment tree.

Try to maintain two segment trees: treeBerland for Berlandia with the rule "on ties — rightmost index", and treeFlatland for Flatlandia with "on ties — leftmost index". Build both from the array strength. Mark section m as INF right away. Keep leftBorder = m. On each move: if B, query the minimum on [1, leftBorder-1] in treeBerland; if F, query the minimum on [leftBorder+1, n] in treeFlatland. Print the returned index, mark it as INF in both trees, and update leftBorder = min(leftBorder, idx). Complexity — 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;
}

All pairs are coprime if and only if no prime number divides two visible numbers at the same time.

Try to maintain divCount[p] — how many active numbers are divisible by p, and a variable conflicts — how many primes have divCount[p] ≥ 2. The answer grows when conflicts == 0.

Compute the smallest prime factor spf[] for all numbers up to 10^7 using a linear sieve. For a query x, obtain the list of its prime divisors. On +x, increment divCount[p] for each divisor. If divCount[p] becomes 2, increment conflicts. On -x, decrement divCount[p]. If divCount[p] becomes 1, decrement conflicts. After processing each command, if conflicts == 0, add 1 to the answer. Complexity — O(MAX + q · log MAX), where 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;
}