Code: Sum of Digits (and Again)

// User : silent_wood
// Submission : https://codeforces.com/contest/2204/submission/366956223

#include <bits/stdc++.h>

constexpr int N = 1e6;
std::array<int, N> d;
std::array<std::array<int, 10>, N> mp;
std::array<std::array<int, 10>, N> smp;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int T;
    std::cin >> T;
    for (int i = 1; i < N; i++) {
        d[i] = d[i / 10] + i % 10;
        mp[i] = mp[i / 10];
        mp[i][i % 10]++;
        smp[i] = smp[d[i]];
        for (int j = 0; j < 10; j++) {
            smp[i][j] += mp[i][j];
        }
    }
    while (T--) {
        std::string s;
        std::cin >> s;
        if (s.size() == 1) {
            std::cout << s << std::endl;
            continue;
        }
        std::array<int, 10> cnt;
        cnt.fill(0);
        for (char c : s)
            cnt[c - '0']++;
        int sum = 0;
        for (int i = 0; i < 10; i++)
            sum += cnt[i] * i;
        for (int x = 1; x <= sum; x++) {
            const std::array<int, 10> &cx = smp[x];
            bool flag = false;
            int s = 0;
            for (int i = 0; i < 10; i++) {
                if (cx[i] > cnt[i]) {
                    flag = true;
                    break;
                }
                s += (cnt[i] - cx[i]) * i;
            }
            if (!flag && s == x) {
                std::cerr << x << std::endl;
                for (int i = 9; i >= 0; i--) {
                    while (cnt[i] > cx[i]) {
                        std::cout << i;
                        cnt[i]--;
                    }
                }
                while (x) {
                    std::cout << x;
                    if (x < 10)
                        break;
                    x = d[x];
                }
                std::cout << std::endl;
                break;
            }
        }
    }
    return 0;
}