Public Judge

pjudge

Time Limit: 2 s Memory Limit: 2048 MB Total points: 100 Interactive Hackable ✓
Statistics

这是一道交互题

在通过内鬼的指引到达 P 国以后,你准备参加 Pre-SDOI Training Camp(也被称作 Public Easy Round #2) 的热身赛。在热身赛中,你遇到了一道这样的问题:

  • 给定 $n$ 个运算符 $\operatorname{op}_1,\operatorname{op}_2,\cdots,\operatorname{op}_n$。对于输入的 $n+1$ 个整数 $a_0,a_1,\cdots,a_n$, 你需要计算以下式子的值:

$$\bigg(\ldots\Big(\big((a_0 \,\operatorname{op}_1\, a_1) \,\operatorname{op}_2\, a_2\big) \,\operatorname{op}_3\, a_3\Big) \ldots \,\operatorname{op}_n\, a_n\bigg)\quad \bmod (10^9+7)$$

  • 对于任意 $0 \leq i \leq n$,有 $0 \leq a_i < 10^9+7$。
  • 对于任意 $1 \leq i \leq n$,有 $\operatorname{op}_i \in \{+, \times \}$,即每个运算符均为加号或乘号。

你很快编写出了解决这个问题的程序。不幸的是,由于你在解决完该问题后过于激动,不小心删除了原问题的题面与你的代码,因此你失去了 $n$ 个运算符 $\operatorname{op}_1,\operatorname{op}_2,\cdots,\operatorname{op}_n$ 的信息。好在你刚刚编译出的程序还在,因此你可以通过向你的程序提问来复原出这些运算符。

由于比赛即将结束,而你所编写的程序的效率并不够高,因此你向程序提问的次数不能超过 $Q_{\mathrm{max}} = 600$ 次。

实现细节

这是一道交互题,本题仅支持 C++ 语言。

你需要提交一个程序 operator,其需要包含头文件 operator.h,并实现以下函数:

std::vector <int> solve(int n)
  • 在每组测试数据中,该函数会在程序运行时被调用恰好一次。
  • $\texttt{n}$ 表示运算符的数量 $n$。
  • 其需要返回一个长度恰好为 $n$ 的数组 $O_0, O_1, \cdots, O_{n-1}$,表示你所复原出的运算符 $\operatorname{op}_i$
    • 你需要保证 $O_i \in \{0, 1\}$
    • $O_i = 0$ 表示你所复原出的运算符 $\mathrm{op}_{i+1}$ 为加号 +
    • $O_i = 1$ 表示你所复原出的运算符 $\mathrm{op}_{i+1}$ 为乘号 ×

你可以通过调用以下函数来向交互库发出询问:

int query(std::vector <int> a)
  • 在每组测试数据中,你可以调用该函数不超过 $Q_{\mathrm{max}}$ 次。
  • $\texttt{a}$ 表示你所提问的 $a_0,a_1,\cdots,a_n$。
    • 你需要保证 $\texttt{a.size()}$ 恰好为 $n+1$,且 $0 \leq a_i < 10^9+7$。
  • 该函数将返回一个 $[0,10^9+7)$ 内的值,描述询问的答案取模 $10^9+7$ 后的结果。

保证在最终评测时,对于任意合法的交互过程,交互库所使用的时间不会超过 0.2 秒,空间不会超过 8 MiB

样例交互库

下发文件中包含了样例交互库 grader.cpp,该交互库可以帮助你理解这道题目的题意并测试你的程序。在最终评测时,所使用的交互库与该样例交互库有所不同,你的程序不应依赖该样例交互库的实现。

你可以使用以下命令编译出可执行文件 answer

g++ grader.cpp operator.cpp -o answer -O2

可执行文件 answer 将从标准输入中读入以下格式的输入数据:

  • 输入的第一行包含一个整数 $n$。
  • 接下来一行,包含 $n$ 个整数 $O_1, O_2, \cdots, O_n$,以与函数 query 的返回值格式相同的方式描述每个运算符。

如果你的返回值正确,可执行文件将向标准输出中输出一行一个整数,表示你所进行询问的次数。

I/O 说明

在最终评测时,交互库与你的程序将运行在两个不同的进程中,他们将通过标准输入输出来传递信息。因此,你的程序不应该从标准输入中读入任何信息,也不应该向标准输出中输出任何信息,也不应使用诸如 std::ios::sync_with_stdio(false)std::cin.tie(nullptr) 的函数,否则可能会遇到不可预料的错误。

子任务

对于所有数据,$1 \leq n \leq 600$。

设你的程序所进行询问的次数为 $Q$:

  • 如果你的程序超出了题目的时间限制或空间限制,发生了运行时错误,或最终返回的答案不正确,则得分为 $0$。
  • 否则,你的得分与你进行询问的次数有关:
    • 若 $Q \leq 40$,则得分为 $100$。
    • 若 $40 < Q \leq 45$,则得分为 $95 - (Q-40)^2$
    • 若 $45 < Q \leq 60$,则得分为 $70 - 2(Q-45)$
    • 若 $60 < Q \leq 188$,则得分为 $40 - 5\log_2(Q-59)$
    • 若 $188 < Q \leq 600$,则得分为 $5$
    • 否则得分为 $0$

下图描述了 $30 \leq Q \leq 100$ 时的得分曲线,你可以通过该曲线来参考你的得分。

problem_21634_1.png

Hack

如果你希望在赛后使用 Hack,你需要注意最终评测时交互库所使用的输入格式有所不同。

请使用以下输入格式来提供 Hack 数据:

  • 输入的第一行包含一个整数 $N$。
  • 接下来一行,包含一个长为 $N$ 的,只包含 +x 的字符串 $S$,描述每个运算符。其中 + 表示加法运算 $+$,x 表示乘法运算 $\times $。