Maps.

Luogu

IDLGP9687

Time1000ms

Memory512MB

DifficultyP2

贪心洛谷原创O2优化构造洛谷月赛

小 Y 希望得到一幅地图，这份地图有些与众不同。这份地图是一幅长为 $n$ 个单位，宽为一个单位的网格图，每个网格必须被涂鸦成白色（$0$）或者黑色（$1$）。你希望满足小 Y 的愿望送给他一幅这样的地图，但是这时小 Y 又提出了两点要求： - 对于每个不在网格图两端的白色格子，恰好有 $p$ 个满足它的左右两个格子都被涂鸦成黑色。 - 在满足上述所有条件的情况下，这幅地图从左到右的字符构成的字符串的字典序最小。你心想，这些要求也是小菜一碟，于是开始了你的创作。 ## Input 本题有多组数据。第一行一个正整数 $T$，表示数据组数。对于每组数据：输入共一行两个整数 $n,p$，表示你需要构造的地图的长度和小 Y 对你的要求。 ## Output 对于每组数据：输出一行一个长度为 $n$ 的 01 字符串，表示你构造的地图；如果无法找到任何一幅地图满足小 Y 的要求，输出 $-1$。 [samples] ## Note #### 【样例解释 #1】对于第一组数据：只有位于第 $4$ 个字符上的数，满足本身是 $0$，不在地图边缘且周围两个都是 $1$，因此符合条件。可以证明这是满足条件的字典序最小的方案。对于第三组数据：可以证明没有任何一个解满足长度为 $5$ 且有 $3$ 个数本身是 $0$，不在地图边缘且周围两个字符都是 $1$。 #### 【数据范围】对于所有测试数据，满足 $1 \le T \le 100$，$1 \le n,p \le 10^5$。 **本题开启捆绑测试，所有数据范围均相同的测试点捆绑为一个 $\text{Subtask}$。** 各测试点的附加限制如下表所示。 | 测试点 | $n,p \le$ | | :-----------: | :-----------: | | $1 \sim 3$ | $10$ | | $4 \sim 5$ | $10^3$ | | $6\sim 10$ | $10^5$ |

Samples

Input #1

Output #1

API Response (JSON)

{
  "problem": {
    "name": "Maps.",
    "description": {
      "content": "小 Y 希望得到一幅地图，这份地图有些与众不同。 这份地图是一幅长为 $n$ 个单位，宽为一个单位的网格图，每个网格必须被涂鸦成白色（$0$）或者黑色（$1$）。 你希望满足小 Y 的愿望送给他一幅这样的地图，但是这时小 Y 又提出了两点要求： - 对于每个不在网格图两端的白色格子，恰好有 $p$ 个满足它的左右两个格子都被涂鸦成黑色。 - 在满足上述所有条件的情况下，这幅地图从左到右的字符",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P2"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9687"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "小 Y 希望得到一幅地图，这份地图有些与众不同。\n\n这份地图是一幅长为 $n$ 个单位，宽为一个单位的网格图，每个网格必须被涂鸦成白色（$0$）或者黑色（$1$）。\n\n你希望满足小 Y 的愿望送给他一幅这样的地图，但是这时小 Y 又提出了两点要求：\n\n- 对于每个不在网格图两端的白色格子，恰好有 $p$ 个满足它的左右两个格子都被涂鸦成黑色。\n- 在满足上述所有条件的情况下，这幅地图从左到右的字符...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments