### A. Очередь на пуфболQueue for Puffball↵
↵
**Idea:** [user:Arbuzik342,2026-10-04]↵
**Preparation:** [user:Arbuzik342,2026-10-04], [user:zeyd1234,2026-10-04]↵
↵
<spoiler summary="Подсказка 1">↵
Посчитайте для каждой семьи две величины: сколько её представителей в очереди и на какой позиции стоит самый первый.↵
</spoiler>↵
↵
<spoiler summary="Подсказка 2">↵
Сортировка семей двухуровневая: сначала по количеству (по убыванию), при равенстве — по позиции первого представителя (по возрастанию).↵
</spoiler>↵
↵
<spoiler summary="Решение">↵
Попробуйте завести два массива: `amount[x]` — число людей из семьи `x` и `firstTime[x]` — минимальный индекс, на котором встречается семья `x`. Пройдите по входу один раз и заполните оба. Затем сложите все уникальные номера семей в вектор и отсортируйте их компараторомHint 1">↵
For each family, compute two values: how many of its members are in the queue, and the position of the earliest one.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
The sorting of families is two-level: first by count (descending), and on ties — by the position of the earliest member (ascending).↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
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:↵
↵
```cpp↵
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)`.↵
</spoiler>↵
↵
<spoiler summary="КодCode">↵
```cpp↵
#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;↵
}↵
```↵
</spoiler>↵
↵
---↵
↵
### B.Без лишних сравненийNo Extra Comparisons↵
↵
**Idea:** [user:Arbuzik342,2026-10-04]↵
**Preparation:** [user:Arbuzik342,2026-10-04], [user:zeyd1234,2026-10-04]↵
↵
<spoiler summary="Подсказка 1">↵
Это обычный пузырёк с оптимизацией: после каждого прохода правая часть массива уже отсортирована.↵
</spoiler>↵
↵
<spoiler summary="Подсказка 2">↵
Границей следующего прохода служит индекс последнего обмена в текущем проходе. Если обменов не было — сортировка завершена.↵
</spoiler>↵
↵
<spoiler summary="Решение">↵
Промоделируйте процесс. Пусть `limit` — количество пар для просмотра в текущем проходе. Изначально `limit = n - 1`. На каждом проходе пробегайтеHint 1">↵
This is the ordinary bubble sort with an optimization: after each pass, the right part of the array is already sorted.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
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.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
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²)` в худшем случае, но при `n ≤ 1000` этого достаточноin the worst case, but with `n ≤ 1000` this is more than enough.↵
</spoiler>↵
↵
<spoiler summary="КодCode">↵
```cpp↵
#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;↵
}↵
```↵
</spoiler>↵
↵
---↵
↵
### C.Вспомни алфавитRemember the Alphabet↵
↵
**Idea:** [user:Arbuzik342,2026-10-04]↵
**Preparation:** [user:Arbuzik342,2026-10-04], [user:zeyd1234,2026-10-04]↵
↵
<spoiler summary="Подсказка 1">↵
Алфавит — линейная цепочка: у каждой буквы максимум один «следующий» и максимум один «предыдущий».↵
</spoiler>↵
↵
<spoiler summary="Подсказка 2">↵
Проверьте три вещи: нет развилок, нет слияний, обход от начала цепочки покрывает все встречающиеся буквы и не натыкается на цикл.↵
</spoiler>↵
↵
<spoiler summary="Решение">↵
Постройте ориентированный граф на 26 буквах. Для каждой пары `(X, Y)` проверьте: у `X` ещё нет исходящего ребра в другую букву; у `Y` ещё нет входящего ребра из другой буквы. Иначе — `NO`. После добавления всех рёбер найдите единственную букву с `in-degree = 0` и пройдите по цепочке, помечая посещённые. Если наткнулись на уже посещённую букву — цикл. Если длина обхода меньше общего числа встречающихся букв — потерялась компонента. В обоих случаяхHint 1">↵
The alphabet is a linear chain: each letter has at most one "next" and at most one "previous".↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
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.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
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`.↵
</spoiler>↵
↵
<spoiler summary="КодCode">↵
```cpp↵
#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;↵
}↵
```↵
</spoiler>↵
↵
---↵
↵
### D.Открой кейсы выгодноOpening Cases Is Profitable↵
↵
**Idea:** [user:Arbuzik342,2026-10-04]↵
**Preparation:** [user:Arbuzik342,2026-10-04], [user:zeyd1234,2026-10-04]↵
↵
<spoiler summary="Подсказка 1">↵
Рассмотрите задачу как DP по префиксу: `best[i]` — лучший ответ для первых `i` кейсовHint 1">↵
Treat the problem as a prefix DP: `best[i]` — the best answer for the first `i` cases.↵
</spoiler>↵
↵
<spoiler summary="Подсказка 2">↵
Если открыть `i`-й кейс, следующие `m` пропускаются. ПереходHint 2">↵
If you open case `i`, the next `m` are skipped. Transition: `best[i] = max(best[i-1], value[i] + best[i-m-1])`.↵
</spoiler>↵
↵
<spoiler summary="Решение">↵
Классическая задача о «взять или пропустить с блокировкой». Попробуйте вести `best[i]` — максимальная сумма на префиксе длины `i`. Для каждого `i`: либо не берём `i`-й кейс (`best[i-1]`), либо берём его и перескакиваем `m` следующихSolution">↵
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)]`).Ответ — `best[n]`. Значения сумм могут достигатьThe answer is `best[n]`. The sums can reach `10^14`, нуженso `long long` is required.↵
</spoiler>↵
↵
<spoiler summary="КодCode">↵
```cpp↵
#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;↵
}↵
```↵
</spoiler>↵
↵
---↵
↵
### E.Горы ФлатландииMountains of Flatland↵
↵
**Idea:** [user:Arbuzik342,2026-10-04]↵
**Preparation:** [user:Arbuzik342,2026-10-04], [user:zeyd1234,2026-10-04]↵
↵
<spoiler summary="Подсказка 1">↵
В задаче `n · m ≤ 10^5`, значит можно спокойно пройтись по всей матрице один разHint 1">↵
In this problem `n · m ≤ 10^5`, so you can safely traverse the entire matrix once.↵
</spoiler>↵
↵
<spoiler summary="Подсказка 2">↵
Для каждой высоты запомните ячейку с минимальным номером столбца, а при равенстве — с минимальным номером ряда.↵
</spoiler>↵
↵
<spoiler summary="Решение">↵
Пройдитесь по матрице и попробуйте завести `map<int, pair<int,int>>`, где ключ — высота, а значение — координаты `(row, col)`. При встрече новой высоты записывайте её. При повторной — сравнивайте: если новая ячейка лучше по столбцу, или равна по столбцу и лучше по строке, обновляйте. На запросы отвечайте заHint 2">↵
For each height, remember the cell with the smallest column index, and on ties — the smallest row index.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
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`.↵
</spoiler>↵
↵
<spoiler summary="КодCode">↵
```cpp↵
#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;↵
}↵
```↵
</spoiler>↵
↵
---↵
↵
### F.Разрушение мостаBridge Destruction↵
↵
**Idea:** [user:Arbuzik342,2026-10-04]↵
**Preparation:** [user:Arbuzik342,2026-10-04], [user:zeyd1234,2026-10-04]↵
↵
<spoiler summary="Подсказка 1">↵
Поддерживайте переменную `leftBorder` — минимальный номер уже разрушенной секции. Берляндия работает наHint 1">↵
Maintain a variable `leftBorder` — the smallest index among destroyed sections. Berlandia works on `[1, leftBorder-1]`,Флатландия — наFlatlandia works on `[leftBorder+1, n]`.↵
</spoiler>↵
↵
<spoiler summary="Подсказка 2">↵
При равенстве прочностей Берляндия выбирает самую правую секцию, Флатландия — самую левую. Храните в дереве отрезков пару `(значение, индекс)`.↵
</spoiler>↵
↵
<spoiler summary="Решение">↵
Попробуйте завести два дерева отрезков: `treeBerland` для Берляндии с правилом «при равенстве — правый индекс», `treeFlatland` для Флатландии — «при равенстве — левый». Оба стройте по массиву `strength`. Секцию `m` сразу помечайте `INF`. Переменная `leftBorder = m`. На каждый ход: если `B`, запрашивайте минимум наHint 2">↵
On ties in strength, Berlandia picks the rightmost section, Flatlandia picks the leftmost. Store a pair `(value, index)` in the segment tree.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
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`. Полученный индекс выводите, помечайте `INF` в обоих деревьях, обновляйтеPrint the returned index, mark it as `INF` in both trees, and update `leftBorder = min(leftBorder, idx)`. СложностьComplexity — `O((n + q) log n)`.↵
</spoiler>↵
↵
<spoiler summary="КодCode">↵
```cpp↵
#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;↵
}↵
```↵
</spoiler>↵
↵
---↵
↵
### G.Просто не простоSimple but Not Simple↵
↵
**Idea:** [user:Arbuzik342,2026-10-04]↵
**Preparation:** [user:Arbuzik342,2026-10-04], [user:zeyd1234,2026-10-04]↵
↵
<spoiler summary="Подсказка 1">↵
Все пары взаимно просты тогда и только тогда, когда ни одно простое число не делит одновременно два видимых числаHint 1">↵
All pairs are coprime if and only if no prime number divides two visible numbers at the same time.↵
</spoiler>↵
↵
<spoiler summary="Подсказка 2">↵
Попробуйте завести `divCount[p]` — сколько активных чисел делятся на `p`, и переменную `conflicts` — сколько простых имеют `divCount[p] ≥ 2`. Ответ растёт, когда `conflicts == 0`.↵
</spoiler>↵
↵
<spoiler summary="Решение">↵
Линейным решетом считайте наименьший простой делитель `spf[]` для всех чисел до `10^7`. Для запроса `x` получайте список его простых делителей. При `+x` увеличивайте `divCount[p]` для каждого делителя. Если `divCount[p]` стало равно `2`, увеличивайтеHint 2">↵
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`.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
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]` стало равно `1`, уменьшайте `conflicts`. После обработки каждой команды, если `conflicts == 0`, добавляйте `1` к ответу. Сложность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`.↵
</spoiler>↵
↵
<spoiler summary="КодCode">↵
```cpp↵
#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;↵
}↵
```↵
</spoiler>↵
↵
↵
**Idea:** [user:Arbuzik342,2026-10-04]↵
**Preparation:** [user:Arbuzik342,2026-10-04], [user:zeyd1234,2026-10-04]↵
↵
<spoiler summary="
Посчитайте для каждой семьи две величины: сколько её представителей в очереди и на какой позиции стоит самый первый.↵
</spoiler>↵
↵
<spoiler summary="Подсказка 2">↵
Сортировка семей двухуровневая: сначала по количеству (по убыванию), при равенстве — по позиции первого представителя (по возрастанию).↵
</spoiler>↵
↵
<spoiler summary="Решение">↵
Попробуйте завести два массива: `amount[x]` — число людей из семьи `x` и `firstTime[x]` — минимальный индекс, на котором встречается семья `x`. Пройдите по входу один раз и заполните оба. Затем сложите все уникальные номера семей в вектор и отсортируйте их компаратором
For each family, compute two values: how many of its members are in the queue, and the position of the earliest one.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
The sorting of families is two-level: first by count (descending), and on ties — by the position of the earliest member (ascending).↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
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:↵
↵
```cpp↵
if (amount[a] != amount[b]) return amount[a] > amount[b];↵
return firstTime[a] < firstTime[b];↵
```↵
↵
</spoiler>↵
↵
<spoiler summary="
```cpp↵
#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;↵
}↵
```↵
</spoiler>↵
↵
---↵
↵
### B.
↵
**Idea:** [user:Arbuzik342,2026-10-04]↵
**Preparation:** [user:Arbuzik342,2026-10-04], [user:zeyd1234,2026-10-04]↵
↵
<spoiler summary="
Это обычный пузырёк с оптимизацией: после каждого прохода правая часть массива уже отсортирована.↵
</spoiler>↵
↵
<spoiler summary="Подсказка 2">↵
Границей следующего прохода служит индекс последнего обмена в текущем проходе. Если обменов не было — сортировка завершена.↵
</spoiler>↵
↵
<spoiler summary="Решение">↵
Промоделируйте процесс. Пусть `limit` — количество пар для просмотра в текущем проходе. Изначально `limit = n - 1`. На каждом проходе пробегайте
This is the ordinary bubble sort with an optimization: after each pass, the right part of the array is already sorted.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
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.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
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`
↵
</spoiler>↵
↵
<spoiler summary="
```cpp↵
#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;↵
}↵
```↵
</spoiler>↵
↵
---↵
↵
### C.
↵
**Idea:** [user:Arbuzik342,2026-10-04]↵
**Preparation:** [user:Arbuzik342,2026-10-04], [user:zeyd1234,2026-10-04]↵
↵
<spoiler summary="
Алфавит — линейная цепочка: у каждой буквы максимум один «следующий» и максимум один «предыдущий».↵
</spoiler>↵
↵
<spoiler summary="Подсказка 2">↵
Проверьте три вещи: нет развилок, нет слияний, обход от начала цепочки покрывает все встречающиеся буквы и не натыкается на цикл.↵
</spoiler>↵
↵
<spoiler summary="Решение">↵
Постройте ориентированный граф на 26 буквах. Для каждой пары `(X, Y)` проверьте: у `X` ещё нет исходящего ребра в другую букву; у `Y` ещё нет входящего ребра из другой буквы. Иначе — `NO`. После добавления всех рёбер найдите единственную букву с `in-degree = 0` и пройдите по цепочке, помечая посещённые. Если наткнулись на уже посещённую букву — цикл. Если длина обхода меньше общего числа встречающихся букв — потерялась компонента. В обоих случаях
The alphabet is a linear chain: each letter has at most one "next" and at most one "previous".↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
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.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
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`.↵
</spoiler>↵
↵
<spoiler summary="
```cpp↵
#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;↵
}↵
```↵
</spoiler>↵
↵
---↵
↵
### D.
↵
**Idea:** [user:Arbuzik342,2026-10-04]↵
**Preparation:** [user:Arbuzik342,2026-10-04], [user:zeyd1234,2026-10-04]↵
↵
<spoiler summary="
Рассмотрите задачу как DP по префиксу: `best[i]` — лучший ответ для первых `i` кейсов
Treat the problem as a prefix DP: `best[i]` — the best answer for the first `i` cases.↵
</spoiler>↵
↵
<spoiler summary="
Если открыть `i`-й кейс, следующие `m` пропускаются. Переход
If you open case `i`, the next `m` are skipped. Transition: `best[i] = max(best[i-1], value[i] + best[i-m-1])`.↵
</spoiler>↵
↵
<spoiler summary="
Классическая задача о «взять или пропустить с блокировкой». Попробуйте вести `best[i]` — максимальная сумма на префиксе длины `i`. Для каждого `i`: либо не берём `i`-й кейс (`best[i-1]`), либо берём его и перескакиваем `m` следующих
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)]`).
</spoiler>↵
↵
<spoiler summary="
```cpp↵
#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;↵
}↵
```↵
</spoiler>↵
↵
---↵
↵
### E.
↵
**Idea:** [user:Arbuzik342,2026-10-04]↵
**Preparation:** [user:Arbuzik342,2026-10-04], [user:zeyd1234,2026-10-04]↵
↵
<spoiler summary="
В задаче `n · m ≤ 10^5`, значит можно спокойно пройтись по всей матрице один раз
In this problem `n · m ≤ 10^5`, so you can safely traverse the entire matrix once.↵
</spoiler>↵
↵
<spoiler summary="
Для каждой высоты запомните ячейку с минимальным номером столбца, а при равенстве — с минимальным номером ряда.↵
</spoiler>↵
↵
<spoiler summary="Решение">↵
Пройдитесь по матрице и попробуйте завести `map<int, pair<int,int>>`, где ключ — высота, а значение — координаты `(row, col)`. При встрече новой высоты записывайте её. При повторной — сравнивайте: если новая ячейка лучше по столбцу, или равна по столбцу и лучше по строке, обновляйте. На запросы отвечайте за
For each height, remember the cell with the smallest column index, and on ties — the smallest row index.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
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)`
</spoiler>↵
↵
<spoiler summary="
```cpp↵
#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;↵
}↵
```↵
</spoiler>↵
↵
---↵
↵
### F.
↵
**Idea:** [user:Arbuzik342,2026-10-04]↵
**Preparation:** [user:Arbuzik342,2026-10-04], [user:zeyd1234,2026-10-04]↵
↵
<spoiler summary="
Поддерживайте переменную `leftBorder` — минимальный номер уже разрушенной секции. Берляндия работает на
Maintain a variable `leftBorder` — the smallest index among destroyed sections. Berlandia works on `[1, leftBorder-1]`,
</spoiler>↵
↵
<spoiler summary="
При равенстве прочностей Берляндия выбирает самую правую секцию, Флатландия — самую левую. Храните в дереве отрезков пару `(значение, индекс)`.↵
</spoiler>↵
↵
<spoiler summary="Решение">↵
Попробуйте завести два дерева отрезков: `treeBerland` для Берляндии с правилом «при равенстве — правый индекс», `treeFlatland` для Флатландии — «при равенстве — левый». Оба стройте по массиву `strength`. Секцию `m` сразу помечайте `INF`. Переменная `leftBorder = m`. На каждый ход: если `B`, запрашивайте минимум на
On ties in strength, Berlandia picks the rightmost section, Flatlandia picks the leftmost. Store a pair `(value, index)` in the segment tree.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
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]`
</spoiler>↵
↵
<spoiler summary="
```cpp↵
#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;↵
}↵
```↵
</spoiler>↵
↵
---↵
↵
### G.
↵
**Idea:** [user:Arbuzik342,2026-10-04]↵
**Preparation:** [user:Arbuzik342,2026-10-04], [user:zeyd1234,2026-10-04]↵
↵
<spoiler summary="
Все пары взаимно просты тогда и только тогда, когда ни одно простое число не делит одновременно два видимых числа
All pairs are coprime if and only if no prime number divides two visible numbers at the same time.↵
</spoiler>↵
↵
<spoiler summary="
Попробуйте завести `divCount[p]` — сколько активных чисел делятся на `p`, и переменную `conflicts` — сколько простых имеют `divCount[p] ≥ 2`. Ответ растёт, когда `conflicts == 0`.↵
</spoiler>↵
↵
<spoiler summary="Решение">↵
Линейным решетом считайте наименьший простой делитель `spf[]` для всех чисел до `10^7`. Для запроса `x` получайте список его простых делителей. При `+x` увеличивайте `divCount[p]` для каждого делителя. Если `divCount[p]` стало равно `2`, увеличивайте
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`.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
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`.
</spoiler>↵
↵
<spoiler summary="
```cpp↵
#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;↵
}↵
```↵
</spoiler>↵
↵
