CF2065E Skibidus and Rizz

With the approach of Valentine's Day, Skibidus desperately needs a way to rizz up his crush! Fortunately, he knows of just the way: creating the perfect Binary String! Given a binary string $ ^{\text{∗}} $ $ t $ , let $ x $ represent the number of $ \texttt{0} $ in $ t $ and $ y $ represent the number of $ \texttt{1} $ in $ t $ . Its balance-value is defined as the value of $ \max(x-y, y-x) $ . Skibidus gives you three integers $ n $ , $ m $ , and $ k $ . He asks for your help to construct a binary string $ s $ of length $ n+m $ with exactly $ n $ $ \texttt{0} $ 's and $ m $ $ \texttt{1} $ 's such that the maximum balance-value among all of its substrings $ ^{\text{†}} $ is exactly $ k $ . If it is not possible, output -1. $ ^{\text{∗}} $ A binary string only consists of characters $ \texttt{0} $ and $ \texttt{1} $ . $ ^{\text{†}} $ A string $ a $ is a substring of a string $ b $ if $ a $ can be obtained from $ b $ by the deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.

The first line contains an integer $ t $ ( $ 1 \leq t \leq 10^4 $ ) — the number of test cases. The first and only line of each test case contains three integers $ n $ , $ m $ , and $ k $ ( $ 0 \leq n, m \leq 2\cdot 10^5 $ , $ 1 \leq k \leq n + m $ , $ n+m\geq 1 $ ). It is guaranteed that the sum of $ n $ and the sum of $ m $ over all test cases does not exceed $ 2\cdot 10^5 $ .

For each test case, if it is possible to construct $ s $ , output it on a new line. If there are multiple possible $ s $ , output any. Otherwise, output -1 on a new line.

In the first test case, we must construct $ s $ such that it contains one $ \texttt{0} $ , two $ \texttt{1} $ , and a maximum balance of $ 1 $ among all of its substrings. One possible valid $ s $ is $ \texttt{101} $ because: - Consider the substring bounded by indices $ [1, 1] $ . Its balance-value is $ \max(0 - 1, 1 - 0) = 1 $ . - Consider the substring bounded by indices $ [1, 2] $ . Its balance-value is $ \max(1 - 1, 1 - 1) = 0 $ . - Consider the substring bounded by indices $ [1, 3] $ . Its balance-value is $ \max(1 - 2, 2 - 1) = 1 $ . - Consider the substring bounded by indices $ [2, 2] $ . Its balance-value is $ \max(1 - 0, 0 - 1) = 1 $ . - Consider the substring bounded by indices $ [2, 3] $ . Its balance-value is $ \max(1 - 1, 1 - 1) = 0 $ . - Consider the substring bounded by indices $ [3, 3] $ . Its balance-value is $ \max(0 - 1, 1 - 0) = 1 $ . Among all possible substrings, the maximum balance-value is $ 1 $ . In the second test case, the substring with the maximum balance-value is $ 0100 $ , which has a balance of $ max(3-1, 1-3)=2 $ .