3599. 百万皇后

单测试点时限: 10.0 秒

内存限制: 256 MB

还是皇后问题。

还是只需要输出任意一个解。

但是这次的规模变成了百万的数量级。

你有最多 秒的时间和 M 的内存。

不需要算出一共有多少种摆放,只要输出任意一种合法的摆放。

输入

只有 行,为 个整数,表示 的皇后规模,

输出

只有 行。

输出任意一种可能的摆放,是 个数( ),用空格分隔,分别表示第 行的皇后摆放在第 列。

行与列的下标从 开始,到

如果没有可能的摆放,输出-1

样例

Input
4
Output
1 3 0 2
Input
2
Output
-1

提示

如果为了得到百万皇后的摆放,你的程序对于较小的 是不适用的,你只需要关心 较大时候的正确性,可以不对 较小时候做特别的优化。

换句话说,例如你的程序对 是不适用的,你不需要特判 时调用回溯或者深搜,你甚至可以任由程序死循环或者奔溃,你只需要保证对于较大规模的皇后问题能在规定时间内得到解。

(当然更严谨的做法是,对于较小规模的 采用回溯等方法,对于超过一定规模的 采用你的程序。正如对于快速排序,小于一定规模的时候会直接调用插入排序等)

12 人解决,25 已尝试。

24 份提交通过,共有 162 份提交。

8.8 EMB 奖励。

创建: 6 月,2 周前.

修改: 5 月,1 周前.

最后提交: 1 天,1 小时前.

来源: 数据结构上机实践课程(2018年秋)

标签