You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

时间限制： 1.0 秒

空间限制： 256 MB

题目描述

已知一个长度为 $n$ 的正整数向量 $a_0,...,a_{n-1}$，给定一个正整数 $k$，你需要设计一个就地算法，让该向量循环左移 $k$ 位。

每次循环左移 1 位的效果为：将数组中所有元素依次向左移动 1 位，并将 $a_0$ 放在 $n-1$ 的位置，使操作完的向量长度同样为 $n$。

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

交互方式

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

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

你需要实现一个函数 void shift(int, int)，传入的第一个参数为向量长度 $n$，第二个参数为 $k$；在该函数中完成对数组的循环左移。

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

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

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

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

白盒交互库实例

具体请见附加文件区的 interactor.cc 和 shift.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,k$，再输入向量的 $n$ 个数，输出 $n$ 个数为最终向量的样子。

3 2
5 0 3

3 5 0

5 7
1 2 3 4 5

3 4 5 1 2

子任务

对于所有数据，保证 $1\le n,a_i\le 10^5,~1\le k\le 2^{31}-1$。

提示

Chap 01，绪论，就地算法，习题 [1-26]。

结合教材第 1 章的就地算法 reverse 进行实现。