UOJ Logo Universal Online Judge

UOJ

#620. 【JOISC2021】方向 2

附件下载 统计

这是一道通信题。

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 可以采取以下五种行动之一:

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

由于时间紧急,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$ 组测试数据,对于每组测试数据,评测库将恰好调用 AnnaBruno 各一次。

特别的,样例交互库对于每组测试数据将先后调用 AnnaBruno 各一次,因此 AnnaBruno 将被交替调用恰好 $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

1
5 7
1 1
1 2
2 1
2 2
2 3
3 2
3 3
1 1

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}$