{"problem":{"name":"H. Hard Drive","description":{"content":"Pia is getting ready for her flight to the NWERC 2018 in Eindhoven. As she is packing her hard drive, she remembers the airline's ridiculous weight restrictions, which may pose a problem. You see, the","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10248H"},"statements":[{"statement_type":"Markdown","content":"Pia is getting ready for her flight to the NWERC 2018 in Eindhoven. As she is packing her hard drive, she remembers the airline's ridiculous weight restrictions, which may pose a problem. You see, the hard drive is essentially a string of ones and zeros, and its weight depends on the number of \"bit changes\" in it: for any two adjacent bits storing two different values, the hard drive gets slightly heavier, so Pia cannot just store arbitrary information on it.\n\nTo make matters worse, the drive is so old that some bits are already broken and will always store zeros. The first bit will never be broken, but the last bit will always be.\n\nPia decides to treat this situation as a challenge: she is now trying to modify the information on the hard drive so that it has exactly the maximum number of bit changes permitted by the airline. However, the broken bits make this harder than expected, so she needs your help.\n\nFind a bit pattern which can be stored on the hard drive and has exactly the desired number of bit changes.\n\nThe input consists of: \n\nOutput a bit string of length $n$, representing Pia's hard drive and containing exactly $c$ bit changes. If there are multiple valid solutions, you may output any one of them. It is guaranteed that at least one solution exists.\n\n## Input\n\nThe input consists of:    One line with three integers $n$, $c$, and $b$ ($2 <= n <= 5 dot.op 10^5$, $1 <= c, b <= n -1$),   the size of the hard drive in bits, the desired amount of bit changes, and the number of broken bits. The positions on the hard drive are numbered from $1$ to $n$.   One line with $b$ integers $z_1, \\\\dots, z_b$ ($2 <= z_1 < z_2 < \\\\dots < z_b = n$), the positions of the broken bits on the hard drive. \n\n## Output\n\nOutput a bit string of length $n$, representing Pia's hard drive and containing exactly $c$ bit changes. If there are multiple valid solutions, you may output any one of them. It is guaranteed that at least one solution exists.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ D = [0, w] \\times [0, h] $ be the rectangular door.  \nLet $ W = \\{ (x_{1,i}, y_{1,i}), (x_{2,i}, y_{2,i}) \\}_{i=1}^n $ be the set of $ n $ wires, where each wire connects two distinct sides of $ D $, and no endpoint lies at a corner or within $ 10^{-6} $ of a corner.  \n\n**Constraints**  \n1. $ 1 \\le n \\le 10^6 $, $ 1 \\le w, h \\le 10^8 $  \n2. For each wire $ i $:  \n   - $ 0 \\le x_{1,i}, x_{2,i} \\le w $, $ 0 \\le y_{1,i}, y_{2,i} \\le h $  \n   - The endpoints lie on different sides of the rectangle (i.e., one on left/right, the other on top/bottom, or one on top/bottom and the other on left/right)  \n   - No endpoint coincides with a corner or another wire endpoint (all points are distinct)  \n\n**Objective**  \nFind the minimum number $ k $ of straight line segments (cuts) such that:  \n- Each cut connects two different sides of $ D $ (i.e., is a chord crossing the rectangle)  \n- Each cut intersects every wire in $ W $  \n- No cut endpoint is within $ 10^{-6} $ of any wire endpoint or corner  \nOutput $ k $ and the $ k $ cuts as line segments $ (x_1, y_1) \\to (x_2, y_2) $, with endpoints on different sides of $ D $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10248H","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}