P10330 [UESTCPC 2024] Black-and-White Bead String

You are a craftsman in Kuanzhai Alley. One day, a customer orders a black-and-white bead string from you. The black-and-white bead string looks like a chain, with black and white beads arranged on it. The customer also gives you $k$ requirements, and each requirement is as follows: - Given $x, y$, there must exist at least one substring in the bead string such that the substring has length $x$ and contains exactly $y$ black beads. Here, a substring means a contiguous segment of beads in the bead string. Please construct a black-and-white bead string that satisfies all the requirements above, and make the length of the string as small as possible. To ensure that your constructed string satisfies the requirements, you also need to give, for each requirement, the position of one substring that satisfies it.

The first line contains an integer $k$ $(1\leq k\leq 10^5)$, representing the number of requirements. The next $k$ lines follow. The $i$-th line contains two integers $x_i,y_i$ $(1\leq x_i\leq 10^6,0\leq y_i\leq x_i)$, representing the $i$-th requirement.

The first line contains an integer $l$, representing the minimum length of a black-and-white bead string that satisfies the requirements. The second line contains a string consisting of ```0``` and ```1```, with length $l$, representing the black-and-white bead string you constructed. Here, ```0``` means a white bead, and ```1``` means a black bead. The next $k$ lines follow. The $i$-th line contains an integer $p_i$, representing the starting position of a substring that satisfies the $i$-th requirement. The positions in the bead string are numbered starting from $0$.

Translated by ChatGPT 5