1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
//: Potyczki Algorytmiczne 2022
// MUZ
#include <cstdio>
#include <deque>

std::deque<unsigned int> tones{};

int min_possible_tone(int prev_tone, int bits)
{
    int poss_tone{ prev_tone + 1 };
    while (__builtin_popcount(poss_tone) != bits)
    {
        ++poss_tone;
    }
    return poss_tone;
}

bool oddaj(int index, int new_tone)
{
    if (index >= tones.size())
    {
        return false;
    }

    if (index + 1 < tones.size())
    {
        int updated_tone{ min_possible_tone(tones[index + 1], __builtin_popcount(tones[index]) + 1) };
        while (updated_tone > tones[index + 1] + 1)
        {
            int remaining_bits{ __builtin_popcount(updated_tone) };
            bool changed{};
            for (int poss_tone = tones[index + 1] + 1; poss_tone < updated_tone; ++poss_tone)
            {
                if (poss_tone < new_tone)
                {
                    if (__builtin_popcount(poss_tone) == (remaining_bits - 1))
                    {
                        if (oddaj(index + 1, poss_tone))
                        {
                            tones[index] = poss_tone;
                            updated_tone = tones[index];
                            changed = true;
                        }
                    }
                }
            }
            if (!changed)
            {
                break;
            }
        }

        if (updated_tone < new_tone)
        {
            tones[index] = updated_tone;
            return true;
        }
        else
        {
            return oddaj(index + 1, tones[index]);
        }
    }
    else
    {
        int updated_tone{ min_possible_tone(0, __builtin_popcount(tones[index]) + 1) };
        if (updated_tone < new_tone)
        {
            tones[index] = updated_tone;
            return true;
        }
        else
        {
            return false;
        }
    }
}

int main()
{
    int n{};
    std::scanf("%d", &n);

    unsigned int next_tone{ 1 };
    while (n > 0)
    {
        int bits{ __builtin_popcount(next_tone) };
        if (bits <= n)
        {
            tones.push_front(next_tone);
            n -= bits;
            ++next_tone;
        }
        else
        {
            unsigned int prev_tone{ tones.front() }; tones.pop_front();
            bits = __builtin_popcount(prev_tone);
            n += bits;
            int first_tone{ min_possible_tone(tones.front(), n) };
            tones.push_front(first_tone);

            while (tones[0] > tones[1] + 1)
            {
                int remaining_bits{ __builtin_popcount(tones[0]) };
                bool changed{};
                for (int poss_tone = tones[1] + 1; poss_tone < tones[0]; ++poss_tone)
                {
                    if (__builtin_popcount(poss_tone) == (remaining_bits - 1))
                    {
                        if (oddaj(1, poss_tone))
                        {
                            tones[0] = poss_tone;
                            changed = true;
                            break;
                        }
                    }
                    else if ((__builtin_popcount(poss_tone) == remaining_bits) && poss_tone < tones[0])
                    {
                        tones[0] = poss_tone;
                    }
                }
                if (!changed)
                {
                    break;
                }
            }

            break;
        }
    }

    std::printf("%lu\n", tones.size());
    for (auto tone : tones)
    {
        std::printf("%u ", tone);
    }
    std::printf("\n");
}