Bittijono

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

int main() {
  ll tavoite;
  cin >> tavoite;
  if (tavoite == 1) {
      cout << tavoite << endl;
      return 0;
  }
  ll pituus = 1;
  ll maara = 1;
  ll prev0 = 2;
  ll prev1 = 1;
  while (maara < tavoite) {
      pituus++;
      if (pituus % 2 == 1) {
          maara += prev1;
          prev0 += prev1;
      } else {
          maara += prev0;
          prev1 += prev0;
      }
  }
  deque<array<ll, 4>> jonot;
  ll lyhinPituus = 40;
  ll lyhimmanArvo = 0;
  //summa, prev0, prev1, arvo
  jonot.push_front({1, 2, 1, 1});
  while (jonot.size() > 0) {
      //cout << jonot.size() << endl;
      array<ll, 4> arvot = jonot.back();
      jonot.pop_back();
      ll maara1 = arvot[0] + arvot[1];
      ll arvo1 = 2 * arvot[3];
      ll jononPituus1 = log(arvo1)/log(2) + 1;
      ll maara2 = arvot[0] + arvot[2];
      ll arvo2 = arvo1 + 1;
      ll jononPituus2 = log(arvo2)/log(2) + 1;
      if (maara1 == tavoite) {
          if (jononPituus1 == pituus) {
              string jono = bitset<64>(arvo1).to_string();
              jono.erase(0, 64 - pituus);
              cout << jono << endl;
              return 0;
          } else if (jononPituus1 < lyhinPituus) {
              lyhinPituus = jononPituus1;
              lyhimmanArvo = arvo1;
          }
      } if (maara2 == tavoite) {
          if (jononPituus2 == pituus) {
              string jono = bitset<64>(arvo2).to_string();
              jono.erase(0, 64 - pituus);
              cout << jono << endl;
              return 0;
          } else {
              if (jononPituus2 < lyhinPituus) {
                  lyhinPituus = jononPituus2;
                  lyhimmanArvo = arvo2;
              }
          }
      } if (maara1 < tavoite && jononPituus1 < lyhinPituus) {
          jonot.push_back({maara1, arvot[1], arvot[1] + arvot[2], arvo1});
      } if (maara2 < tavoite && jononPituus2 < lyhinPituus) {
          jonot.push_back({maara2, arvot[1] + arvot[2], arvot[2], arvo2});
      }
  }
  string jono = bitset<64>(lyhimmanArvo).to_string();
  jono.erase(0, 64 - lyhinPituus);
  cout << jono << 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