#P18583. Binary Substrings

Binary Substrings

Binary Substrings

给定正整数 nn,请构造一个长度为 nn、仅由 0 和 1 组成的字符串,使它的不同非空连续子串数量尽可能多。

子串按字符串内容区分;相同内容即使出现在不同位置,也只计一次。

输入格式

输入一个整数 nn,1≤n≤2×1051\le n\le2\times10^5。输入只包含一组数据。

输出格式

输出一个长度为 nn 的二进制字符串,其不同非空子串数量在所有长度为 nn 的二进制字符串中最大。

有多种最优答案时,输出任意一种。请输出构造出的字符串,而不是子串数量。

样例输入 1

2

样例输出 1

01

样例输入 2

5

样例输出 2

00110

样例说明

第一组的不同非空子串为 0、1、01,共3个。

第二组按长度分组,不同子串的个数依次为 2,4,3,2,12,4,3,2,1,合计12个。例如长度2的子串是 00、01、11、10。