A. Maximal Binary Matrix

Codeforces

IDCF803A

Time1000ms

Memory256MB

Difficulty—

constructive algorithms

English · Original

Chinese · Translation

Formal · Original

You are given matrix with _n_ rows and _n_ columns filled with zeroes. You should put _k_ ones in it in such a way that the resulting matrix is symmetrical with respect to the main diagonal (the diagonal that goes from the top left to the bottom right corner) and is lexicographically maximal. One matrix is lexicographically greater than the other if the first different number in the first different row from the top in the first matrix is greater than the corresponding number in the second one. If there exists no such matrix then output _\-1_. ## Input The first line consists of two numbers _n_ and _k_ (1 ≤ _n_ ≤ 100, 0 ≤ _k_ ≤ 106). ## Output If the answer exists then output resulting matrix. Otherwise output _\-1_. [samples]

给你一个大小为 #cf_span[n] × #cf_span[n] 的矩阵，初始时所有元素均为 0。你需要在其中放置 #cf_span[k] 个 1，使得结果矩阵关于主对角线（从左上角到右下角的对角线）对称，并且字典序最大。如果一个矩阵在从上到下第一个不同的行中，第一个不同的元素大于另一个矩阵对应位置的元素，则称该矩阵字典序更大。如果不存在这样的矩阵，则输出 _-1_。第一行包含两个数 #cf_span[n] 和 #cf_span[k]（#cf_span[1 ≤ n ≤ 100]，#cf_span[0 ≤ k ≤ 106]）。如果答案存在，请输出得到的矩阵；否则输出 _-1_。 ## Input 第一行包含两个数 #cf_span[n] 和 #cf_span[k]（#cf_span[1 ≤ n ≤ 100]，#cf_span[0 ≤ k ≤ 106]）。 ## Output 如果答案存在，请输出得到的矩阵；否则输出 _-1_。 [samples]

**Definitions** Let $ n \in \mathbb{Z}^+ $, $ k \in \mathbb{Z}_{\geq 0} $. Let $ A \in \{0,1\}^{n \times n} $ be a binary matrix. **Constraints** 1. $ A $ is symmetric: $ A_{i,j} = A_{j,i} $ for all $ i,j \in \{1, \dots, n\} $. 2. $ \sum_{i=1}^n \sum_{j=1}^n A_{i,j} = k $. 3. $ A $ is lexicographically maximal among all symmetric $ n \times n $ binary matrices with exactly $ k $ ones. **Objective** If such a matrix $ A $ exists, output $ A $. Otherwise, output $-1$.

Samples

Input #1

2 1

Output #1

1 0 
0 0

Input #2

3 2

Output #2

1 0 0 
0 1 0 
0 0 0

Input #3

2 5

Output #3

\-1

API Response (JSON)

{
  "problem": {
    "name": "A. Maximal Binary Matrix",
    "description": {
      "content": "You are given matrix with _n_ rows and _n_ columns filled with zeroes. You should put _k_ ones in it in such a way that the resulting matrix is symmetrical with respect to the main diagonal (the diago",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF803A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given matrix with _n_ rows and _n_ columns filled with zeroes. You should put _k_ ones in it in such a way that the resulting matrix is symmetrical with respect to the main diagonal (the diago...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "给你一个大小为 #cf_span[n] × #cf_span[n] 的矩阵，初始时所有元素均为 0。你需要在其中放置 #cf_span[k] 个 1，使得结果矩阵关于主对角线（从左上角到右下角的对角线）对称，并且字典序最大。\n\n如果一个矩阵在从上到下第一个不同的行中，第一个不同的元素大于另一个矩阵对应位置的元素，则称该矩阵字典序更大。\n\n如果不存在这样的矩阵，则输出 _-1_。\n\n第一行包含两个数...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $, $ k \\in \\mathbb{Z}_{\\geq 0} $.  \nLet $ A \\in \\{0,1\\}^{n \\times n} $ be a binary matrix.  \n\n**Constraints**  \n1. $ A $ is symmetric: $ A_{i,j} = A_{j,i} $ ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments