P9868 [NOIP2023] Dictionary

Xiao S has $n$ pairwise distinct words $w_1, w_2, \cdots, w_n$ in the dictionary, each with length $m$. Each word is a string consisting of lowercase letters. Xiao S may perform the following operation any number of times (possibly zero times): choose any word in the dictionary and swap any two characters in it. For each $1 \le i \le n$, Xiao S wants to know whether it is possible, through the operations above, to obtain $n$ new words $w'_1, w'_2, \cdots, w'_n$ such that for every $j \ne i$, $w'_i$ is lexicographically smaller than $w'_j$. **For the case $n = 1$, we agree that the property above naturally holds.** For two strings of the same length $s = s_1 s_2 \cdots s_L$ and $t = t_1 t_2 \cdots t_L$, we say that $s$ is lexicographically smaller than $t$ if and only if the following holds: there exists a position $i$ such that $s$ and $t$ are identical before the $i$-th character, and $s_i < t_i$, i.e., the lowercase letter $s_i$ comes before $t_i$ in alphabetical order.

The first line contains two positive integers $n$ and $m$, representing the number of words and the length of each word. The next $n$ lines each contain a lowercase string $w_i$ of length $m$, representing a word.

Output one line containing a `01` string $a$ of length $n$. For $1 \le i \le n$, if the property described in the statement holds, then $a_i =$ `1`; otherwise, $a_i =$ `0`.

**[Sample Explanation #1]** - Without any operation, the first word is lexicographically smallest, so the first character of the output is `1`. - Swap the first two characters of `bananaa`, and swap the third and sixth characters of `abandon`, obtaining `abondan`, `abnanaa`, `baannaa`, `notnotn`. Now the second word is lexicographically smallest, so the second character of the output is `1`. - Swap the first and last characters of `baannaa` to get `aaannab`, leaving the other strings unchanged. Now the third word is lexicographically smallest, so the third character of the output is `1`. - No matter how you operate, the fourth word will not be smaller than the second word, so the fourth character of the output is `0`. **[Sample Explanation #2]** This sample satisfies the limits of test point $4$. **[Sample Explanation #3]** This sample satisfies the limits of test point $7$. **[Sample Explanation #4]** This sample satisfies the limits of test point $10$. **[Constraints]** For all testdata, it is guaranteed that: $1 \le n \le 3000$, $1 \le m \le 3000$, each $w_i$ is a lowercase string of length $m$, and all words are pairwise distinct. | Test Point ID | $n \leq$ | $m \leq$ | | :----------: | :----------: | :----------: | | $1$ | $1$ | $1$ | | $2 \sim 4$ | $26$ | $1$ | | $5 \sim 7$ | $15$ | $2$ | | $8$ | $300$ | $300$ | | $9$ | $10^3$ | $10^3$ | | $10$ | $3000$ | $3000$ | Translated by ChatGPT 5