#include "dna.h"
#include<bits/stdc++.h>
using namespace std;
int n;
namespace sub1{
string solve(){
for(int mask = 1; mask < (1 << n); mask++){
string s = "";
for(int i = 0; i < n; i++){
s += char((mask >> i & 1) + 48);
}
if(make_test(s)){
return s;
}
}
return string(n, '0');
}
}
namespace sub2{
string solve(){
string s = "";
while(s.size() < n){
s += '0';
if(!make_test(s)){
s.pop_back();
break;
}
}
if(s.empty() || s.size() == n){
return string(n, '0' + s.empty());
}
bool z = true;
while(s.size() < n){
s += char('0' + z);
if(!make_test(s)){
s.pop_back();
s += char('0' + (z = !z));
if(!make_test(s)){
s.pop_back();
break;
}
}
}
z = true;
while(s.size() < n){
s = char('0' + z) + s;
if(!make_test(s)){
s[0] = '0' + (z = !z);
}
}
return s;
}
}
namespace sub3{
string solve(){
int low = 1, high = n, max_zero = 0, cnt_zero = 0;
while(low <= high){
int mid = (low + high) >> 1;
if(make_test(string(mid, '0'))){
low = (max_zero = mid) + 1;
}
else{
high = mid - 1;
}
}
if(max_zero == 0 || max_zero == n){
return string(n, '0' + (max_zero == 0));
}
string s = string(max_zero, '0');
while(true){
if(!make_test(s += '1')){
s.back() = '0';
cnt_zero++;
}
else{
cnt_zero = 0;
}
if(cnt_zero + max_zero >= n || cnt_zero > max_zero){
break;
}
}
high = max_zero;
s = s.substr(low = 0, int(s.size()) - cnt_zero);
cnt_zero = 0;
while(low <= high){
int mid = (low + high) >> 1;
if(make_test(s + string(mid, '0'))){
low = (cnt_zero = mid) + 1;
}
else{
high = mid - 1;
}
}
s += string(cnt_zero, '0');
while(s.size() < n){
s = '0' + s;
if(!make_test(s)){
s[0] = '1';
}
}
return s;
}
}
string analyse(int _n, int t){
n = _n;
if(t == 31){
return sub1::solve();
}
if(t == 256){
return sub2::solve();
}
return sub3::solve();
}
