Sequence Configuration

Time Limit : 1 sec, Memory Limit : 65536 KB

問題 D 列の構成

問題文

1 から N までの相異なる整数が N / 2 個書かれたカードがいくつか与えられるので,次の条件を満たすような長さ N の数列 seq1 つ作って出力して欲しい.

  • seq の各要素は 01 である.
  • すべてのカードについて以下が成り立つ: カードに書かれた数字をcard[1], ..., card[N/2]とする.このときカードに書かれた部分の和: seq[card[1]] + ... + seq[card[N/2]]N / 8 以上かつ 3N / 8 以下になっている.

例えば,N = 8 でカードが 2 枚渡され,カードに書かれている数字がそれぞれ [1, 2, 7, 8][4, 5, 7, 8] であったとする.このとき seq=[0, 1, 0, 1, 0, 1, 0, 1]seq=[0, 0, 0, 0, 1, 1, 1, 1] とおくと条件を満たすようにできている.

入力形式

入力は次の形式で与えられる.
N K
card1[1] card1[2] ... card1[N/2]
card2[1] card2[2] ... card2[N/2]
...
cardK[1] cardK[2] ... cardK[N/2]

1 行目において N は構成するべき数列の長さ,K はカードの枚数である. 続く K 行には各カードの情報が与えられる.cardi[1], ..., cardi[N/2]i 番目のカードに書かれている数字である.

出力形式

seqi 番目の要素が i 文字目に対応するように数列 seq1 行に出力せよ.

なお,どの入力に対しても解は必ず少なくとも 1 つは存在する.

制約

  • 8 ≤ N ≤ 1,000, 1≤ K ≤ N / 2
  • N8 の倍数
  • 1 ≤ cardi[1] < cardi[2] < ... < cardi[N/2] ≤ N

入出力例

入力例 1

8 2
1 2 7 8
4 5 7 8

出力例 1

01010101

入力例 2

8 3
2 3 4 6
3 4 5 8
3 4 6 8

出力例 2

01110011

Source: Kyoto University Programming Contest 2011 , Kyoto, Japan, 2011-08-06
Problem Setter:  Mitsuru Kusumoto ,  Yuichi Yoshida
http://www.kupc.jp/2011.html