Merkkijono

#include <iostream>
#include <stack>
#include <vector>

using namespace std;

struct state
{
	long long int p0;
	long long int p1;
	long long int nodes;
	string route;
};

int target;

int go(int dir, state s, stack<int>* res)
{
	if(dir)
	{
		s.p0 += s.p1;
		s.nodes += s.p1;
	}
	else
	{
		s.p1 += s.p0;
		s.nodes += s.p0;
	}

	//cout << "dir: " << dir << ", p0: " << s.p0 << ", p1: " << s.p1 << ", nodes: " << s.nodes << endl;
	//cout << s.route << endl;
	s.route += (dir ? "1" : "0");

	if(s.nodes > target)
	{
		//cout << "fuck" << endl;
		return 0;
	}

	if(s.nodes == target)
	{
		cout << s.route << endl;
		return 1;
	}

	if(!go(!dir, s, res))
	{
		return go(dir, s, res);
	}
	return 1;
}

int main()
{
	cin >> target;

	stack<int> result;
	go(0, {1, 1, 0, ""}, &result);
}

Test 1

Verdict: WRONG ANSWER

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: WRONG ANSWER

Test 5

Verdict: WRONG ANSWER

Test 6

Verdict: WRONG ANSWER

Test 7

Verdict: WRONG ANSWER

Test 8

Verdict: WRONG ANSWER

Test 9

Verdict: WRONG ANSWER

Test 10

Verdict: WRONG ANSWER