「OICon-02」Pick Stone

Luogu

IDLGP10172

Time1000ms

Memory512MB

DifficultyP4

贪心Special JudgeO2优化构造

小 S 有一个 $n\times m$ 的棋盘。初始每个位置都有一个棋子。每次，小 S 可以取走一个周围（四连通）被取走棋子数不超过 $1$ 的棋子。求小 S 最多能取走多少棋子，并构造一种合法的取棋子方案。 ## Input 一行，两个正整数 $n,m$，表示棋盘大小。 ## Output 第一行一个正整数，表示最多能取走的棋子数 $ans$。接下来 $n$ 行，每行 $m$ 个 $-1\sim ans$ 之间的整数。每个位置的数表示这个位置的棋子是第几个取走的。如果该位置的棋子没被取走，请输出 $-1$。 [samples] ## Note ### 样例解释对于样例 $1$，取出 $(1,1)$ 时周围有 $0$ 个已取出位置，取出 $(1,2),(2,1)$ 时周围有 $1$ 个已取出位置，故原构造符合要求。容易证明没有更优答案。 ### 数据范围 **本题采用捆绑测试。** | $\text{Subtask}$ | 特殊性质 | $\text{Score}$ | |:--:|:--:|:--:| | $1$ | $n=1$ | $20$ | | $2$ | $n=2$ | $30$ | | $3$ | $n=3$ | $50$ | 对于 $100\%$ 的数据：$\bm{1\leq n\leq3}$，$1\leq m\leq10^5$。如果你答对了第一问最多能取走的棋子数而没有正确地构造，你将获得 $70\%$ 的分值。一个子任务你的得分是所有测试点得分的最小值。注意，你仍需要按格式输出 $n\times m$ 个数表示构造方案，我们推荐你全部输出 $-1$。保证 `checker.cpp` 在符合格式要求的输出下用时不超过 $0.5$ 秒。

Samples

Input #1

2 2

Output #1

3
1 2
3 -1

Input #2

3 5

Output #2

12
2 3 4 5 6
1 -1 12 -1 7
8 9 -1 11 10

API Response (JSON)

{
  "problem": {
    "name": "「OICon-02」Pick Stone",
    "description": {
      "content": "小 S 有一个 $n\\times m$ 的棋盘。初始每个位置都有一个棋子。每次，小 S 可以取走一个周围（四连通）被取走棋子数不超过 $1$ 的棋子。求小 S 最多能取走多少棋子，并构造一种合法的取棋子方案。",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10172"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "小 S 有一个 $n\\times m$ 的棋盘。初始每个位置都有一个棋子。每次，小 S 可以取走一个周围（四连通）被取走棋子数不超过 $1$ 的棋子。求小 S 最多能取走多少棋子，并构造一种合法的取棋子方案。\n\n## Input\n\n一行，两个正整数 $n,m$，表示棋盘大小。\n\n## Output\n\n第一行一个正整数，表示最多能取走的棋子数 $ans$。\n\n接下来 $n$ 行，每行 $m$ 个 $...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments