Автор, розробник, автор розбору: Iлля Пермяков

Спочатку помiтимо, що числа, якi не є префiксом жодного iншого числа, не можуть бути у однiй пiдмножинi. Тобто найкраща можлива вiдповiдь це ~cnt~, де ~cnt~ — кiлькiсть таких чисел. Виявляється, що завжди можна побудувати пiдмножини саме з такою вiдповiддю.

Для розв'язання цiєї задачi iснує багато жадiбних алгоритмiв, розглянемо один з них:

1. Видiлимо усi такi числа, що не є префiксом жодного iншого числа. Занесемо цi числа у рiзнi пiдмножини розмiру 1. На початку, вважатимемо, що усi iншi числа не належать жоднiй пiдмножинi.

2. Переберемо цi числа, нехай зараз розглядаємо число ~x~.

3. Далi дивимось на кожне таке ~y~, що є в масивi ~a~, а також є префiксом ~x~. Якщо ~y~ не належить жоднiй пiдмножинi, то додаємо його до пiдмножини ~x~.

Таким чином, можна побачити, що усi числа, якi ми не видiлили, будуть належати одному з ~cnt~ пiдмножин.

Сумарний час роботи рiшення: ~O(n·19·log(n))~ або ~O(n·19)~ в залежностi вiд реалiзацiї.

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

const int N = 2e5+6;
int64_t a[N];
unordered_map<int64_t, int> mp;

signed main(void) {
  cin.tie(0)->sync_with_stdio(false);

  int n;
  cin >> n;
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
  }
  sort(a, a+n, greater<int64_t>());
  for (int i = 0; i < n; ++i) mp[a[i]] = i;
  vector<vector<int64_t>> res;
  vector<bool> mark(n, false);
  for (int i = 0; i < n; ++i) {
    if (mark[i]) continue;
    mark[i] = true;
    vector<int64_t> here={a[i]};
    for (; a[i] > 0; a[i] /= 10) {
      if (!mp.count(a[i])) continue;
      if (mark[mp[a[i]]]) continue;
      mark[mp[a[i]]] = true;
      here.push_back(a[mp[a[i]]]);
    }
    res.push_back(here);
  }
  cout << res.size() << "\n";
  for (auto& x : res) {
    cout << x.size() << "\n";
    for (const int64_t& i : x) cout << i << " ";
    cout << "\n";
  }
}