シーケンスを最小化する (Minimize the Sequence)
与えられた
n 個の数 からなるシーケンスを、できるだけ辞書式順 (lexicographically) で小さくしてください。辞書式順で小さくするには、シーケンス内の 許可された 要素同士を入れ替える (swap) 操作を行います。入れ替えは何度でも行えますが、すべての要素が自由に入れ替えられるわけではなく、入れ替えが許可されている特定のインデックス同士のみが操作可能です。2つのシーケンスの辞書式比較 (Lexicographic comparison of two sequences)
シーケンス がシーケンス より辞書式順で小さいとは、ある整数
k (1 ≤ k ≤ n) が存在して、このとき、入れ替え可能な位置関係を示す行列が与えられています。初期シーケンスから、可能な操作を使って得られるシーケンスの中で、辞書式順がもっとも小さいものを出力してください。
入力
1行目には整数
n (1 ≤ n ≤ 300) が与えられます。2行目には、空白区切りで
n 個の整数 (1 ≤ ≤ n) が与えられます。これは初期シーケンスを表し、数値はすべて異なります。続く
n 行には、各行に n 個の 0 または 1 が与えられます。行 i 列 j の値が 1 のときは、i 番目と j 番目の要素同士の入れ替えが許可されていることを意味し、0 の場合は入れ替えが許可されていないことを意味します。出力
与えられた初期シーケンスから、入れ替え操作によって作ることができる辞書式順でもっとも小さいシーケンスを出力してください。
例
Input | Output |
5
4 2 1 5 3
00100
00011
10010
01101
01010 | 1 2 3 4 5 |
7
5 2 4 3 6 7 1
0001001
0000000
0000010
1000001
0000000
0010000
1001000 | 1 2 4 3 6 7 5 |
解説
- 以下のような入れ替え操作が可能です:
- ↔ ⇒ 1 2 4 5 3
- ↔ ⇒ 1 2 4 3 5
- ↔ ⇒ 1 2 3 4 5
- ↔ ⇒ 1 2 4 5 3
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB