Bases Conversion (ois_23)

/*
 * Public and published.
 * Written by Gabriel Hearot <gabriel@hearot.it>.
 */

#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <vector>

unsigned int T, i, k, c, v;

using namespace std;

#define MAX_BASE_2 16384 // 2**14, half of the maximum number of the digits a number can have in base 2 without being greater than 100_000_000 (base 10)
#define MAX_BASE_3 19683 // 3**9, see MAX_BASE_2

vector<unsigned int> base2{ /* sum of digits up to MAX_BASE_2 */ };

vector<unsigned int> base3{ /* sum of digits up to MAX_BASE_3 */ };

unsigned int sum(unsigned int n, unsigned int base)
{
    if (base == 2)
    {
        if (n <= MAX_BASE_2)
        {
            return base2[n - 1];
        }
        else
        {
            if (n % MAX_BASE_2 == 0)
                return base2[n / MAX_BASE_2 - 1];

            return base2[n % MAX_BASE_2 - 1] + base2[n / MAX_BASE_2 - 1];
        }
    }
    else
    {
        if (n <= MAX_BASE_3)
        {
            return base3[n - 1];
        }
        else
        {
            if (n % MAX_BASE_3 == 0)
                return base3[n / MAX_BASE_3 - 1];

            return base3[n % MAX_BASE_3 - 1] + base3[n / MAX_BASE_3 - 1];
        }
    }
}

int32_t main()
{
    cin >> T;

    vector<unsigned int> input(T);
    vector<unsigned int> keys;
    map<unsigned int, unsigned int> special_numbers;

    for (i = 0; i < T; i++)
    {
        cin >> input[i];

        if (count(keys.begin(), keys.end(), input[i]) == 0)
            keys.push_back(input[i]);

        k = max(k, input[i]);
    }

    priority_queue<unsigned int, vector<int>, greater<unsigned int>> pq;

    for (auto e : keys)
        pq.push(e);

    v = pq.top();
    pq.pop();

    for (i = 1; i <= k; i++)
    {
        if (sum(i, 2) == sum(i, 3))
        {
            c++;
        }

        if (i == v) {
            special_numbers[i] = c;

            if (pq.size() > 0) {
                v = pq.top();
                pq.pop();
            }
        }
    }

    for (i = 0; i < T; i++)
    {
        cout << special_numbers[input[i]] << " ";
    }

    return 0;
}