No.873 バイナリ、ヤバいなり!w

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 37
作問者 : tatyamtatyam / テスター : Shuz*Shuz*
5 ProblemId : 2743 / 出題時の順位表

問題文

バイナリを「0と1のみで構成される文字列」と定義します。
01列を「隣合う文字が相異なるバイナリ」と定義します。
バイナリのヤバさを「バイナリを同じ文字が連続するところで分割したときのそれぞれの01列の長さの二乗和」と定義します。
例えば、 "01011011000" は "0101" , "101" , "10" , "0" , "0"と分割され、そのヤバさは $4^2+3^2+2^2+1^2+1^2=31$ です。
正の整数 $N$ が与えられます。ヤバさが $N$ のバイナリのうち最も長さの短いものを求めてください。
ただし、答えが複数ある場合は、そのうち辞書順最小を求めてください。

入力

$N$

入力は整数で与えられる。
$1\leq N\leq 3 \times 10^5$

出力

最後に改行してください。

サンプル

サンプル1
入力
1
出力
0

ヤバさが 1 であるバイナリは "0" と "1" で、どちらも長さが 1 ですが、辞書順最小である "0" を出力します。

サンプル2
入力
5
出力
001

サンプル3
入力
32
出力
01011010

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。