## B - 01 Graph Construction Editorial by evima

First, initialize \(S = \)`0`

\( \times N\) (a string of \(N\) `0`

s), and \(T = \)`1`

\( \times N\).

From here, we aim to satisfy the conditions by repeatedly performing the following two types of operations:

- Append
`0`

to the end of \(S\), and`0`

to the end of \(T\). - Append
`1`

to the end of \(S\), and`0`

to the end of \(T\).

During the process, we keep track of which connected components the unmatched `0`

s and `1`

s belong to.
Let the connected components to which the unmatched `0`

s on the \(S\) side belong be \(x_1, x_2, \cdots, x_k\) (in the order they appear), and the connected components to which the unmatched `1`

s on the \(T\) side belong be \(y_1, y_2, \cdots, y_k\).

The operation of adding `0`

and `0`

to \(S\) and \(T\), respectively, corresponds to cyclically shifting \(x\) one position to the left.

The operation of adding `1`

and `0`

to \(S\) and \(T\), respectively, corresponds to removing \(x_1\) and \(y_1\) from \(x\) and \(y\), and adding an edge between \(x_1\) and \(y_1\).

By combining these operations, we aim to satisfy the condition of \(A\). First, prepare an appropriate permutation \(P\), ensuring that its cycle decomposition aligns with \(A\). Then, we perform operations to connect \(x_1\) and \(y_1\) at the moment when \(x_1 = A_{y_1}\).

The number of operations is \(O(N^2)\).

posted:

last update: