P16966 [SCCPC 2026] A Defeatless Crown for the Blank

:::align{center}  ::: :::epigraph[No Game No Life] Once the pact is made, may this game be without defeat. :::

In a world where everything is decided by games, Stephanie, Sora, and Shiro are studying a new board game. The board is a $2\times n$ matrix. The cell in row $i$ and column $j$ contains $a_{i,j}$ coins. At the start of the game, the player stands at cell $(1,1)$, and the goal is to move to cell $(2,n)$. In each step, the player can only move one cell to the right, or one cell down. Since the board has only two rows, a legal path is equivalent to choosing a column $k$ where you move down: first walk from $(1,1)$ to $(1,k)$, then move down to $(2,k)$, and finally walk to $(2,n)$. Shiro moves first and collects all coins on her path. After Shiro finishes, Sora moves and collects all coins in cells that were not visited by Shiro. Shiro wants to minimize the number of coins Sora collects, while Sora wants to maximize the number of coins he collects. Stephanie watched carefully for a while, and then confidently proposed a strategy: if Shiro just chooses the path that lets her collect the most coins, wouldn’t she win? Shiro stayed silent for a second and pointed out that this strategy is not always correct. Stephanie, unconvinced, demanded that Shiro immediately give a board such that her strategy would uniquely choose a wrong path. However, Shiro was busy playing against Sora, so she handed this task to you. Now you are given a $2\times n$ board. Some positions on the board are already fixed as positive integers, and the others are $-1$. You need to replace all $-1$ with positive integers in $[1,10^9]$, so that the constructed board satisfies the following conditions: There exists a unique path that makes Shiro’s collected coins as large as possible; and Stephanie’s unique choice is wrong, meaning that there exists another path for Shiro such that the maximum number of coins Sora can obtain is smaller. If it is impossible to construct such a board, output $-1$.

The first line contains an integer $n$ ($1 \le n \le 2\cdot 10^5$), the number of columns of the board. The second line contains $n$ integers $a_{1,1},a_{1,2},\ldots,a_{1,n}$, representing the first row of the board. The third line contains $n$ integers $a_{2,1},a_{2,2},\ldots,a_{2,n}$, representing the second row of the board. For each position, we have $a_{i,j}=-1$, or $1\le a_{i,j}\le 10^9$.

If it is impossible to construct, output one line with a single integer $-1$. Otherwise, output two lines, each with $n$ integers, representing the constructed board.

Translated by ChatGPT 5