Bittijono

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

//tavoite: tavoiteltava summa
//lista: lisätyt luvut
//viimeinen: listan viimeinen luku
//summa: lisättävä summa jos lisätään eri luku kuin viimeinen
//kokonaisSumma: listan kokonaissumma
//raja: raja listan pituudelle (missä vaiheessa lopetetaan etsintä)

array<int, 30> lyhinjono(ll tavoite, deque<int> lista, ll viimeinen, ll summa, ll kokonaissumma, ll raja) {
    int length = lista.size();
    if (kokonaissumma == tavoite) {
        array<int, 30> bittijono;
        bittijono.fill(0);
        int alku = 30 - length;
        int edellinenBitti = 0;
        ll edellinenLuku = 0;
        for (int i = 0; i < length; i++) {
            ll luku = lista.front();
            lista.pop_front();
            if (luku == edellinenLuku) {
                bittijono[alku + i] = edellinenBitti;
            } else {
                edellinenLuku = luku;
                if (edellinenBitti == 0) {
                    bittijono[alku + i] = edellinenBitti = 1;
                } else {
                    edellinenBitti = 0;
                }
            }
        }
        return bittijono;
    }
    if (kokonaissumma > tavoite || length >= raja) {
        array<int, 30> bittijono;
        bittijono.fill(2);
        return bittijono;
    }
    //lisätään eri luku, arvo kasvaa summalla
    lista.push_back(summa);
    array<int, 30> jono1 = lyhinjono(tavoite, lista, summa, summa + viimeinen, kokonaissumma + summa, raja);
    if (jono1[0] != 2) {
        for (ll i = 0; i < 30; i++) {
            if (jono1[i] == 1) {
                if (30 - i < raja) {
                    raja = 30 - i;
                }
                break;
            }
        }
    }
    lista.pop_back();
    lista.push_back(viimeinen);
    array<int, 30> jono2 = lyhinjono(tavoite, lista, viimeinen, summa + viimeinen, kokonaissumma + viimeinen, raja);
    if (jono2[0] != 2) {
        return jono2;
    }
    return jono1;
}

int main() {
    ll tavoite;
    cin >> tavoite;
    ll pituus = 1;
    ll summa = 1;
    ll a = 1;
    ll b = 1;
    while (summa < tavoite) {
        pituus++;
        ll c = a;
        a += b;
        b = c;
        summa += a;
    }
    deque<int> lista;
    lista.push_back(1);
    array<int, 30> jono = lyhinjono(tavoite, lista, 1, 2, 1, pituus + 2);
    for (int i = 0; i < 30; i++) {
        if (jono[i] == 1) {
            a = i;
            break;
        }
    }
    for (int i = a; i < 30; i++) {
        cout << jono[i];
    }
    cout << endl;
}

Test 1

Group: 1

Verdict: ACCEPTED

Test 2

Group: 1

Verdict: ACCEPTED

Test 3

Group: 1

Verdict: ACCEPTED

Test 4

Group: 1

Verdict: ACCEPTED

Test 5

Group: 1

Verdict: ACCEPTED

Test 6

Group: 1

Verdict: ACCEPTED

Test 7

Group: 1

Verdict: ACCEPTED

Test 8

Group: 1

Verdict: ACCEPTED

Test 9

Group: 1

Verdict: ACCEPTED

Test 10

Group: 1

Verdict: ACCEPTED

Test 11

Group: 2

Verdict: ACCEPTED

Test 12

Group: 2

Verdict: ACCEPTED

Test 13

Group: 2

Verdict: ACCEPTED

Test 14

Group: 2

Verdict: ACCEPTED

Test 15

Group: 2

Verdict: ACCEPTED

Test 16

Group: 2

Verdict: ACCEPTED

Test 17

Group: 2

Verdict: ACCEPTED

Test 18

Group: 2

Verdict: ACCEPTED

Test 19

Group: 2

Verdict: ACCEPTED

Test 20

Group: 2

Verdict: ACCEPTED

Test 21

Group: 3

Verdict: ACCEPTED

Test 22

Group: 3

Verdict: ACCEPTED

Test 23

Group: 3

Verdict: ACCEPTED

Test 24

Group: 3

Verdict: ACCEPTED

Test 25

Group: 3

Verdict: ACCEPTED

Test 26

Group: 3

Verdict: ACCEPTED

Test 27

Group: 3

Verdict: ACCEPTED

Test 28

Group: 3

Verdict: ACCEPTED

Test 29

Group: 3

Verdict: ACCEPTED

Test 30

Group: 3

Verdict: ACCEPTED

Test 31

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 32

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 33

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 34

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 35

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 36

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 37

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 38

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 39

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 40

Group: 4

Verdict: TIME LIMIT EXCEEDED