存在する場合はそれを出力し、存在しない場合には何でも良いので出力してくださいという問題を解けばよいです。なぜなら出力の直前にチェックして違反していれば急遽 -1 を出力すれば良いからです。

また、ビットごとに考えて良いですから、\(U _ i, V _ i \in \lbrace 0, 1 \rbrace \ ( i = 1, \dots, n )\) としてよいです。さらに

• 論理積が \(0\) → どれか \(0\)
• 論理積が \(1\) → 全部 \(1\)
• 論理和が \(0\) → 全部 \(0\)
• 論理和が \(1\) → どれか \(1\)

と言い換えておきましょう。

次のように操作します。

1. 「全部〜 」系は該当箇所をそれに従って埋めましょう。ここで矛盾する可能性がありますが、存在しない場合は何を出力しても良いのでオーケーです。
2. 次に「どれか〜」系を処理です。この時点で空マスがなければ終了、残り行数・残り列数のいずれかが \(2\) 以上のときには市松模様で埋めて終了です。
3. 残り行数（残り列数のときも同様）が \(1\) のときには列側の制約を見ます。これが「全部〜」系を埋めた時点で解決している場合は行側の制約に従います。解決していない場合は列側の制約に従います。

以上の操作をすると、存在する場合は条件を満たすものが構成できています。