题目描述

这是一道交互题。

若智是一名炼金术士。

一场大梦过后，他终于发现了单向传送门的打造方法。

若智打造了 $N$ 个传送门，编号为 $0\sim N-1$ 。

刚开始，$i$ 号传送门的等级是 $a_i$ 。

如果一扇传送门的等级为 $l$ ，那么从该传送门进入就会从 $l$ 号传送门出来，此时他的背后就是 $l$ 号传送门。

所以，所有传送门的等级是小于 $N$ 的非负整数。

若智可以运用自己的能力，改变传送门的等级。

但是，打破平衡是炼金术士的大忌，所以如果若智想要把一个传送门的等级增加 $1$ ，那么他就必须在此之前先走进这扇传送门，再转过身把面前的传送门的等级降低 $1$ ，然后走回 $x$ 号传送门，把 $x$ 号传送门的等级提高 $1$ 。

反过来，如果若智想要把一个传送门的等级降低 $1$ ，那么他就必须在此之前先走进这扇传送门，再转过身把面前的传送门的等级提高 $1$ ，然后走回 $x$ 号传送门，把 $x$ 号传送门的等级降低 $1$ 。

当然，为了让所有传送门的等级都是小于 $N$ 的非负整数，所以这里所有的加和减的运算都是在模 $N$ 意义下进行的。

比如说，有 $3$ 个传送门，等级按编号顺序分别为 $1,2,1$ ，那么若智如果想增加 $1$ 号门的等级（此时 $1$ 号门等级为 $2$ ），那么他就要走进 $1$ 号门，然后转身，这样他的面前是 $2$ 号传送门（因为他进了 $1$ 号门之后是从 $2$ 号门出来的），降完 $2$ 号传送门的等级之后再给 $1$ 号传送门升级。于是之后三个门的等级按编号顺序变为了 $1,0,0$ 。

今天是若智的生日，他想对于每个 $i$ 把 $i$ 号传送门的等级改为 $b_i$ 。但是他不知道要怎么才能实现他的目标，所以你可以帮帮他吗？要是帮了他他就请你吃饭哦。

任务介绍

你需要实现一个函数 adjust，来帮助若智调整传送门的等级。

• adjust(N,a,b)
  • N 为传送门的数量，a,b 为题目中描述的两个数组。

在每个测试点中，交互库都会调用 $1$ 次 adjust 函数。

你可以调用函数Inc 和 Dec 来进行修改。

• Inc(x)

  • 把 $x$ 号传送门的等级提高 $1$ 。当然，你需要按照上面的规则先穿过门转身给面前的门降 $1$ 级。

• Dec(x)

  • 把 $x$ 号传送门的等级降低 $1$ 。当然，你需要按照上面的规则先穿过门转身给面前的门升 $1$ 级。

再次注意这里所有的增减操作均在模 $N$ 意义下进行。

注意函数 Inc 和 Dec 不会改变函数 adjust 中形参 a 的内容。

实现细节

本题只支持C++。

源代码中需要包含头文件 portals.h 。

你需要实现下面的函数：

int adjust(int N,int* a,int* b)

对于数组 a 和 b ，你只能访问下标在 $0\sim N-1$ 的位置，否则不保证程序能正常运行。

如果无论如何也不能实现若智的目标，则该函数需要返回 $-1$ ，否则返回 $0$ 。

函数 Inc 的接口如下：

void Inc(int x)

函数 Dec 的接口如下：

void Dec(int x)

如何测试你的程序

你需要在本题目录下使用如下命令编译得到可执行程序：

g++ -o guess grader.cpp guess.cpp

可执行文件将从标准输入读取以下格式的数据：

第一行包含一个正整数 $N$ ，需要保证 $N\le 1000$。

第二行一共 $N$ 个整数，$a_0,a_1,\dots ,a_{N-1}$，需要保证 $0\le a_i<N$ 。

第三行一共 $N$ 个整数，$b_0,b_1,\dots ,b_{N-1}$，需要保证 $0\le b_i<N$ 。

读入完成之后，交互库将会调用 adjust 函数。

接下来交互库将会在标准输出中输出以下信息：

第一行一共 $N$ 个整数，$a_0^{\prime },a_1^{\prime },\dots ,a_{N-1}^{\prime }$，表示你操作之后每个传送门的等级。

第二行形如 cnt tot ，其中 $cnt$ 表示 $a_i^{\prime }$ 与 $b_i$ 相等的 $i$ 的个数，$tot$ 的值等于 $N$ 。

第三行是 adjust 函数的返回值。

交互式类型的题目怎么本地测试

样例源代码

在本题目录下，有C++语言的样例源代码 portals.cpp。按照上文中提到的方式进行编译，即能通过编译得到可执行程序。

样例源代码只是帮助理解题目，结果不一定正确。

样例一

input

3
1 2 1
1 0 0

output

1 0 0
3 3
0

explanation

该样例即题目中描述的例子。

这是使用试题目录的grader和样例源程序得到的输出文件。

评分方式

对于每个测试点，首先交互库会比较 adjust 函数的返回值与正确的返回值。如果正确的返回值是 $0$ 而你没有返回 $0$ ，那么该测试点的得分为 $0$ 。

如果 adjust 的返回值是 $-1$ 且正确的返回值也是 $-1$ ，则该测试点的得分为 $1$ 。

如果 adjust 的返回值是 $0$ 且正确的返回值也是 $0$ ，设 $cnt=\sum _{i=0}^{N-1}[a{\prime }_i=b_i]$，那么你的得分为 $max\{S,0.1\}$ ，这里 $S$ 是关于 $cnt$ 和 $N$ 的函数。不同子任务 $S$ 的计算方式不同。

如果 adjust 的返回值是 $0$ 而正确的返回值是 $-1$ ，那么该测试点的得分为 $S$ 。

每个子任务中 $S$ 的具体计算方法在“限制与约定”中给出。

一个子任务的得分等于该子任务中所有测试点得分的最小值乘以该子任务的满分分值。

限制与约定

保证一个子任务中的测试点不超过 $20$ 个。

子任务 1（20分）：$N\le 8,S={\left(\frac{cnt}{N}\right)}^{2.3}$ 。

子任务 2（20分）：$N\le 25,S={0.9}^{N-cnt}$ 。

子任务 3（20分）：$N\le 200,S=max\{{0.85}^{N-cnt},0.75\times {\left(\frac{cnt}{N}\right)}^{1.5}\}$ 。

子任务 4（40分）：$N\le 1000,S={\left(\frac{cnt}{N}\right)}^3$ 。

时间限制：$\mathtt{\text{1s}}$

空间限制：$\mathtt{\text{512MB}}$

题目中所给的时间、空间限制为你的代码和交互库加起来可以使用的时间和空间。

我们保证，在1s内至少能进行 $2\times {10}^7$ 次的 Inc 函数或 Dec 函数的调用，其余部分交互库运行所用的时间不超过 0.1s，也就是说，选手实际可用的时间至少为0.9s 。

我们保证，对于任何合法的数据及在限制范围内的调用，任何版本的交互库（包括下发给选手的和最终评测使用的）运行所用的空间不会超过12MB，也就是说，选手实际可用的空间至少为500MB。

下载

交互库下载