Bittijono

input/code.cpp: In function 'std::string findBitstring(std::string, int, int)':
input/code.cpp:84:31: warning: variable 'fitIndex' set but not used [-Wunused-but-set-variable]
   int maxFitness = 123456879, fitIndex = -1;
                               ^
input/code.cpp: In function 'int main()':
input/code.cpp:161:8: warning: variable 'foundASuccess' set but not used [-Wunused-but-set-variable]
   bool foundASuccess = false;
        ^

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;
bool foundBySearching = false;
size_t foundAtIndex = 0;

int n;

int bounds[27] = {1, 3, 6, 11, 19, 32, 53, 87, 142, 231, 375, 608, 985, 1595, 2582, 4179,
              6763, 10944, 17709, 28655, 46366, 75023, 121391, 196416, 317809, 514227, 832038};

int numberOfDistinct(const string& str)
{
	int ones = 0;
	int zeros = 0;
	int distinct = 0;
	
	for (size_t i = 0; i < str.length(); i++)
	{
		char bit = str[i];
		bool isOne = bit == '1';
		
		int newSum = 1 + distinct;
		distinct = distinct - (isOne ? ones : zeros) + newSum;
		if (distinct == n)
		{
			foundBySearching = true;
			foundAtIndex = i;
			return 0;
		}
		if (isOne) ones = newSum;
		else zeros = newSum;
	}
	
	return distinct;
}

int binSizeLowerBound(int n)
{
	for (int i = 26; i != 0; i--)
	{
		int bound = bounds[i];
		if (bound < n)
		{
			return i + 1;
		}
	}
	return 1;
}

int customPow(int base, int exponent)
{
	if (exponent == 0) return 1;
	int res = base;
	while (exponent != 1)
	{
		res *= base;
		exponent--;
	}
	return res;
}

string convertToBitString(size_t value)
{
	string str(32, '0');
	
	for (size_t i = 0; i < 32; i++)
	{
		if ((1LL << i) & value)
			str[31 - i] = '1';
	}
	str = str.substr(str.find_first_not_of("0"));
	
	return str;
}


string findBitstring(string b, int n, int tries)
{
	for (int test = 0; test < tries; test++)
	{
		int maxFitness = 123456879, fitIndex = -1;
		while (true)
		{
			bool foundImprovement = false;
			for (size_t i = 1; i < b.size(); i++)
			{
				char bit = b[i];
				b[i] = (bit == '1') ? '0' : '1';
				
				int distinctSubs = numberOfDistinct(b);
				if (foundBySearching == true) return b.substr(0, foundAtIndex + 1);
				//cout << b << " : " << distinctSubs << "\n";
				
				int fitness = abs(distinctSubs - n);
				if (fitness == 0)
				{
					// Solution found.
					return b;
				}
				if (fitness < maxFitness)
				{
					maxFitness = fitness;
					fitIndex = (int)i;
					foundImprovement = true;
				}
				
				//b[i] = bit;
			}
			
			if (!foundImprovement)
			{
				//cout << "No improvement found :-( shuffling\n";
				random_shuffle(b.begin() + 1, b.end());
				break;
			}
		}
	}
	return "fail";
}


int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	/*
	long n;
	cin >> n;*/
	//int base = (int)log2(n);
	
	//cout << base << "\n";
	//int n;
	//cin >> n;
	cin >> n;
	bool found = false;
	string chainString = "1100101010110101001001101010110110101011100110011010001010110100101101010111010011010101010010110110101001011000101010101001011100010010101101010110010010010100101001100101100110101110101100101011010101010101001001001001011011001010110100011010010101101010100101010100101010101110010101010110100110001110010101001101010101010101001010101100100010010011010110101011101010100101010010011001010011001010110101010100101110100110101101010100010100110011101011001010101010010101011001101110011010010011010101100110011001010101011001010101110010101110100101011001010101101010010011010110110011010101010110001110101010010110011001110101011011011011010101011101101101010001010101100110001100100101011010101010101101011101101101101010110011101010100110010101001010100101100110110101011100010101101000101011000101010110101010100010110101101010110101101110101011010101000100010101011010100101010101110010101011011001101010101110100100101010101010101110011010111010010101010100101010101100110111010110100110010101001010011101010100101010110100010010100101101101001011001100101011101010110010110011011010101110010110100101101010011011001101010101100101001010100110100111010110101001000110101110101010010001011101010111010101010101011001010101001010100101001010110010101101010110101100001010100101100100110010110101101011001010110111000101101010101010010101010010101001010010110100101010110100010010100101010010010010100010011010101010111101011010010101001010101010";
	string alternating = "101010101010101010101010101010";
	
	//cout << chainString.size() << "\n";
	size_t chainSize = chainString.size();
	size_t chainTapeLen = 29;
	/*
	int lowerBound = 50000;
	int upperBound = 1000000;
	
	
	for (int n = 999999; n < upperBound; n += 10000)
	{*/
		int len = binSizeLowerBound(n);
		int low = len + 1;
		int high = len + 2;
		
		for (int i = 0; i < 27; i++)
			if (bounds[i] == n) found = true;
		
		
		bool foundASuccess = false;
		if (n == 1) cout << "1";
		else if (found) cout << alternating.substr(0, low);
		else
		{
			for (size_t i = 0; i < (chainSize / chainTapeLen); i++)
			{
				string p1 = chainString.substr(chainTapeLen * i, low);
				string p2 = chainString.substr(chainTapeLen * i, high);
				string p3 = chainString.substr(chainTapeLen * i, high + 1);
				string p4 = chainString.substr(chainTapeLen * i, high + 2);
				
				string res1 = findBitstring(p1, n, 750);
				if (res1 == "fail")
				{
					res1 = findBitstring(p2, n, 750);
				}
				
				if (res1 == "fail")
					res1 = findBitstring(p3, n, 750);
				
				if (res1 == "fail")
					res1 = findBitstring(p4, n, 750);
				
				if (res1 != "fail")
				{
					cout << res1 << "\n";
					foundASuccess = true;
					break;
				}
			}
		}
		/*
		if (!foundASuccess)
		{
			cout << n << " : fail\n";
		}*/
	//}
	/*	
	cout << findBitstring("010101010100000001010101010", 832038, 1000) << "\n";
	cout << findBitstring("100010001000100010001000100", 832038, 1000) << "\n";
	cout << findBitstring("010101010100000001010101010", 832038, 1000) << "\n";
	cout << findBitstring("010101010100000001010101010", 832038, 1000) << "\n";*/

	
	//cout << m << "\n";
	//cout << numberOfDistinct(str) << "\n";
	
	return 0;
}

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: WRONG ANSWER

Test 28

Group: 3

Verdict: ACCEPTED

Test 29

Group: 3

Verdict: ACCEPTED

Test 30

Group: 3

Verdict: ACCEPTED

Test 31

Group: 4

Verdict: WRONG ANSWER

Test 32

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 33

Group: 4

Verdict: ACCEPTED

Test 34

Group: 4

Verdict: WRONG ANSWER

Test 35

Group: 4

Verdict: WRONG ANSWER

Test 36

Group: 4

Verdict: WRONG ANSWER

Test 37

Group: 4

Verdict: WRONG ANSWER

Test 38

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 39

Group: 4

Verdict: WRONG ANSWER

Test 40

Group: 4

Verdict: WRONG ANSWER