时间限制： 1.0 秒

空间限制： 256 MB

题目背景

已知一个长度为 $n$ 的正整数向量 $a_0,...,a_{n-1}$，给定一个正整数 $k$，你需要设计一个就地算法，将数组进行冲排序，将所有的奇数集中放在数组前端，将所有的偶数都集中放在数组后端。

为了保证你的算法是就地算法，我们会在交互方式上进行限制。

交互方式

这是一道函数式交互题，不需要选手考虑输入输出，也不要从标准输入读入数据，或将任何内容输出到标准输出，否则会影响判题。

你提交的代码需要包含头文件 sort.h。

你需要实现一个函数 void sort(int)，传入的第一个参数为向量长度 $n$；在该函数中完成按奇偶排序。

你可以调用函数 void swapval(int, int)，传入参数为两个介于 $0$ 到 $n-1$ 的整数 $x,y$，交换当前向量中 $x$ 位置和 $y$ 位置的值。当 swapval 调用次数超过 $\lceil 1.5n\rceil$，或传入参数越界，则会报 Runtime Error。

你可调用函数 bool isodd(int) 和 bool iseven(int)，传入参数均为介于 $0$ 到 $n-1$ 的整数 $x$，分别判断当前向量 $x$ 位置的值是否为奇数或是否为偶数。当 isodd 和 iseven 调用总次数超过 $\lceil 1.5n\rceil$，或传入参数越界，则会报 Runtime Error。

以下我们给出一个代码提交实例（会固定交换依次 $0$ 和 $n-1$ 位置的值，仅作为示例，不保证能得分）：

#include "sort.h"
void shift(int n, int k)
{
    swapval(0, n - 1);
}

你不需要，也不应该，实现主函数。

白盒交互库实例

具体请见附加文件区的 interactor.cc 和 sort.h。本题直接采用白盒交互库进行评测。

如果你本地的实现代码为 main.cc，则将交互库放在同一目录下，在 Linux 系统中输入以下命令行即可运行：

g++ main.cc interactor.cc -Wall -std=c++20 -o foo -lm -O2 -I/include

在 Windows 下会生成 foo.exe，在 Linux 下会生成 foo，你可以输入 .\foo.exe 或者 ./foo 命令行执行该文件。或者将交互库接口与你实现的函数统一在单代码文件中进行本地调试即可。

白盒交互库先输入 $n$，再输入向量的 $n$ 个数，输出 $n$ 个数为最终向量的样子。

9
2 13 7 4 6 3 7 12 9

9 13 7 7 3 6 4 12 2

样例 1 解释

最终的向量只要满足奇数全在前面，偶数全在后面即可。你只需要输出任意一种符合限制的答案均为正确。

子任务

对于所有数据，保证 $1\le n,a_i\le 10^5$。

来源

清华《数据结构》期中 2011 - 算法大题（1）