3599. 百万皇后

单点时限: 10.0 sec

内存限制: 256 MB

还是皇后问题。

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

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

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

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

输入格式

只有 $1$ 行,为 $1$ 个整数,表示 $n \times n$ 的皇后规模, $ 1 \leqslant n \leqslant 3000000$。

输出格式

只有 $1$ 行。

输出任意一种可能的摆放,是 $n$ 个数( $x_0, x_1,\cdots, x_{n-1}$ ),用空格分隔,分别表示第 $i$ 行的皇后摆放在第 $x_i$ 列。

行与列的下标从 $0$ 开始,到 $n-1$。

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

样例

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

提示

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

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

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

27 人解决,67 人已尝试。

43 份提交通过,共有 343 份提交。

6.4 EMB 奖励。

创建: 6 年,4 月前.

修改: 6 年,3 月前.

最后提交: 3 月前.

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

题目标签