P15418 「yrOI R1」消融于夜色
题目背景
题目描述
给你一个 $n \times m$ 的网格，你需要在网格上放置若干个国际象棋中的王，使得每个王的攻击范围内有且仅有 $k$ 个王。
你需要构造使得你放置王的数量 $ \ge z$，给出任意一种方案即可。
注：国际象棋中的王的攻击范围为距离它切比雪夫距离为 $1$ 的格子。
输入格式
输入只有一行，输入四个整数 $n,m,k,z$。
输出格式
第一行你需要输出一个数代表你构造的方案王的个数。
你需要输出一个 $n \times m$ 的 $01$ 方阵，代表你构造的网格，$0$ 代表此处不放置王，$1$ 代表此处放置王。
请保证你构造的网格符合题目限制，否则你将会得到 $0$ 分。
说明/提示
**【数据范围】**
本题只有两个测试点：
+ 测试点 1（20 pts）：$k=2$，$n=m=1003$，$z=5\times10^5$。
+ 测试点 2（55 pts）：$k=3$，$n=1003$，$m=1004$，$z=5\times10^5$。
记你输出的方案王的个数为 $y$，你将会得到此测试点 $\min(100,\left \lfloor \frac{-10^6}{y-z-10^4} \right \rfloor)\%$ 的分数。