【JOISC2021】方向 2 - 题目 - Universal Online Judge

这是一道通信题。

JOI 王国是一个被海环绕的岛国，它的土地是一个 $N$ 行 $N$ 列的网格。第 $r+1$ 行第 $c+1$ 列的方格用 $(r,c)$ 表示。

JOI 王国的女王 Anna 邀请了 Bruno 参加聚会。她选择了 $K(=7)$ 个方格作为可能举办聚会的地点，候选地点用 $0\cdots K-1$ 编号，候选地点均不在边界上。为了帮助 Bruno，在派对的前一天 Anna 将在每个方格放上一种旗帜，并在旗帜上写入整数 $x\in[1,10^9]$。聚会当天，Bruno 将被告知聚会地点的编号，并随机出现在一个不在边界上的位置。

Bruno 并不知道他的具体位置，但是他知道东南西北的方向。同时，他可以看到周围和所在位置共 $9$ 个方格的旗帜，即如果他在 $(a,b)(1\leq a,b\leq N-2)$，它可以看到 $(a − 1, b − 1), (a − 1, b), (a − 1, b + 1), (a, b − 1), (a, b), (a, b + 1), (a + 1, b − 1), (a + 1, b), (a + 1, b + 1)$ 位置的旗帜。

Bruno 可以采取以下五种行动之一：

移动到 $(a, b+1)$。
移动到 $(a, b-1)$。
移动到 $(a+1, b)$。
移动到 $(a-1, b)$。
认为当前位置就是聚会举办地点，停止移动。

由于时间紧急，Bruno 走的路径必须是某条最短路。因此，Bruno 一定不会经过网格边缘。

由于写大整数很麻烦，Anna 想要最小化写下整数的最大值。请你写一个程序来给出 Anna 的标号方案和 Bruno 的行动策略。

任务

本题仅支持符合 C++ 11 标准及以上的 C++ 语言。

你需要提交两份源文件。

Alice

第一个源文件名为 Alice.cpp，该程序将扮演 Anna 的角色。你必须引用 Alice.h。

你需要实现下面的过程：

void Anna(int N, int K, std::vector<int> R, std::vector<int> C);

$N$ 表示网格大小，$K(=7)$ 表示候选地点的个数。

$R$ 和 $C$ 是两个长度为 $K$ 的数组，表示编号为 $i$ 的候选地点为 $(R_i,C_i)$。

你可以调用如下函数：

void setFlag(int r, int c, int value);

这个函数的作用设置方格旗帜的整数。

$r,c$ 表示设置的方格是 $(r,c)$，若参数不满足 $0\leq r,c\lt N$，程序将被判为 Wrong Answer[1]。

$value$ 表示旗帜上要写的整数，若参数不满足 $1\leq \textrm{value}\leq 10^9$，程序将被判为 Wrong Answer[2]。

对于一次 Anna 的调用，一组 $(r,c)$ 不能被调用两次，否则将被判为 Wrong Answer[3]。

对于一次 Anna 的调用，setFlag 将被恰好调用 $N^2$ 次，否则将被判为 Wrong Answer[4]。

如果在 Anna 的调用中程序被判为了 Wrong Answer，程序将立刻结束。

Bruno

你需要实现如下过程：

std::vector<int> Bruno(int K, std::vector<int> value);

这个函数应当返回 Bruno 的下一步行动。对于每次 Anna 的调用，这个函数会被调用恰好一次。

参数 $K(=7)$ 表示候选聚会地点的个数，$\textrm{value}$ 是一个长度为 $9$ 的数组，描述了 Bruno 所在位置周围的旗帜。具体的，$\textrm{value}$ 数组的内容依次为 $(a−1, b−1), (a−1, b), (a−1, b+1), (a, b−1), (a, b), (a, b+1), (a+1, b−1), (a+1, b), (a+1, b+1)$ 九个格子的旗帜颜色。

函数的返回值应当为一个长度为 $K$ 的数组，否则程序将被判为 Wrong Answer[5]。

返回的元素均为 $0$ 到 $4$ 之间的整数，否则程序将被判为 Wrong Answer[6]。

数组的第 $i+1$ 个元素应当为若聚会地点的编号为 $i$，Bruno 的下一步行动是什么。如果 Bruno 不在聚会地点但是停止了行动，或他的行动不可能成为最短路，程序将被判为 Wrong Answer[7]。

每个测试点包含了 $Q$ 组测试数据，对于每组测试数据，评测库将恰好调用 Anna 和 Bruno 各一次。

特别的，样例交互库对于每组测试数据将先后调用 Anna 和 Bruno 各一次，因此 Anna 和 Bruno 将被交替调用恰好 $Q$ 轮。

评测方式

样例评测库的编译方式为：

g++ grader.cpp Anna.cpp Bruno.cpp -o grader -std=c++17 -fsigned-char -O2

样例输入

第一行一个整数 $Q$ 表示数据组数。

对于每组数据：

第一行两个整数 $N,K$，表示网格大小和候选地点个数。

接下来 $K$ 行每行两个整数 $R_i,C_i$，表示候选地点的坐标。

样例输出

若交互过程不合法，将输出 Wrong Answer 并接上错误编号。

否则输出形如 Accepted: Maximum value = 12 的信息表示使用的最大整数。

样例一

input

explanation

`Anna` 的调用	`Bruno` 的调用	返回值
`Anna(5,7,[1,1,2,...,3],[1,2,1,...,3])`	$~$	$~$
`SetFlag(0,0,47)`	$~$	$~$
`SetFlag(0,1,15)`	$~$	$~$
`SetFlag(0,2,63)`	$~$	$~$
$\dots$	$~$	$~$
`SetFlag(4,4,89)`	$~$	$~$
$~$	`Bruno(7,[47,15,63,...,71])`	$[4,0,2,2,2,0,0]$

Anna 的设置的旗帜值为：

47 15 63 56 71
10 46 52 18 67
63 56 71 19 48
52 18 67 99 26
71 19 48 60 89

数据范围与提示

本题只有一个子任务。

保证 $1\leq Q\leq 300, 5\leq N\leq 100, K=7, 1\leq R_i,C_i,a,b\leq N-2,\forall 0\leq x,y\lt K, (R_x,C_x)\neq (R_y,C_y)$。

设 $Q$ 组数据中，你使用的最大整数为 $L$，则你在这个测试点的得分如下：

若 $70000\lt L\leq 10^9$，得 $7$ 分。

若 $10000\lt L\leq 70000$，得 $13$ 分。

若 $2000\lt L\leq 10000$，得 $19$ 分。

若 $20\lt L\leq 2000$，得 $50-12.5\times \log_{10}\left(\frac{L}{20}\right)$ 分。

若 $L\leq 20$，得分如下表：

$L$	$20$	$19$	$18$	$17$	$16$	$15$	$14$	$13$	$\leq 12$
$\textrm{score}$	$50$	$53$	$56$	$60$	$64$	$69$	$75$	$85$	$100$

保证对于合法的调用，评测库不会使用超过 $0.5s$ 的时间和 $512MB$ 空间。

hack

hack 数据格式与样例输入相同。

hack 成功后，请联系管理员添加数据至 hack 数据。

时间限制：两个程序的时间限制分别为 $\texttt{1s}$

空间限制：两个程序的空间限制分别为 $\texttt{512MB}$

Universal Online Judge

UOJ

#620. 【JOISC2021】方向 2

任务