3005 「JOISC 2015 Day 4」Limited Memory

译自 JOISC 2015 Day4 T2「Limited Memory」。

注意：在 LibreOJ 上，由于语言限制，目前只支持以下语言的提交： - C - C++ - C++ (NOI) - C++ 11 - C++ 11 (Clang) - C++ 11 (NOI) - C++ 17 - C++ 17 (Clang)

JOI 酱被选为了日本代表去参加国际信息学奥林匹克竞赛。为了提高信息处理速度，日本国际信息学奥林匹克竞赛委员会的 K 理事长提出了一个课题。

K 理事长在纸上写下了一个字符串 $ S $，仅由 <，>，[ 和 ] 组成，但是 JOI 酱不知道字符串具体是什么。JOI 酱会被告知字符串的长度，他的课题是判断字符串 $ S $ 是不是一个合法字符串。合法字符串的定义如下：

• 空字符串（长度为 $ 0 $ 的字符串）是合法字符串。
• 假设 $ x $ 是一个合法字符串，那么 <$x$> 也是合法字符串。
• 假设 $ x $ 是一个合法字符串，那么 [$x$] 也是合法字符串。
• 假设 $ x $ 和 $ y $ 都是合法字符串，那么 $xy$ 也是合法字符串。

例如 <>[] 和 [<>]<> 都是合法字符串，而 >< 和 [<]> 都不是合法字符串。

每天的中午，JOI 酱可以给 K 理事长打一个电话。电话里，JOI 酱可以指定一个整数 $ I $，K 理事长会告诉他字符串 $ S $ 的第 $ I $ 个字符。

现在 JOI 酱有一个限制：不能用其它东西记录这个课题相关的笔记。JOI 酱每天晚上 $22$ 点睡觉，早上 $6$ 点起床。在睡眠中，她只能在脑中记下 $ 22 $ 比特的信息。更准确的说，她会在睡前把一个 $0$ 到 $ 2^{22}-1 $ 的整数记在脑内，然后第二天醒来根据这个整数来做决策。由于字符串长度是一开始就被告知的，JOI 酱是一直知道这个信息的。

JOI 酱每天睡前可以记住一个整数，或者发邮件告诉 K 理事长字符串 $ S $ 是不是一个合法字符串。在后者的情况下，这个课题就结束了，K 理事长会判定你是否完成了这个课题。注意，邮件必须在课题开始后 $ 15000 $ 天内发给 K 理事长，不然你就算没有完成这个课题。

任务

请编写一个程序实现 JOI 酱的策略，并正确解出上述课题。

实现细节

你需要实现一个过程来确定字符串是否正确。请包含头文件 memory.h。

程序需要实现以下过程。

• int Memory(int N, int M)
• 参数 $ N $ 表示字符串 $ S $ 的长度。
• 参数 $ M $ 表示上一天睡前记下的整数，在课题一开始的时候 $ M = 0 $。
• 在这个函数里必须恰好调用一次 Get 函数。
• 函数的返回值必须是一个 $ 0 $ 到 $ 2^{22} - 1 $ 的整数，或者 $ -1 $，或者 $ -2 $。如果返回值不在这些数里面，那么你的程序会被判为 Wrong Answer [1]。
  • 返回值是 $ 0 $ 到 $ 2^{22} - 1 $ 的整数的话，表示这是睡前记下的数字。
  • 返回值是 $ -1 $ 的话，表示用邮件回答 $ S $ 是一个合法字符串。
  • 返回值是 $ -2 $ 的话，表示用邮件回答 $ S $ 不是一个合法字符串。
• 这个函数应该理论上只依赖 $ N $，$ M $ 和 Get 的返回值进行决策。在实际评测过程中这个函数会被调用 $ 2^{22} \times 4$ 次，更详细的信息请参考「评分的顺序」。

此外，程序中可以调用如下函数。

• char Get(int I)
• 这个函数只能在调用 Memory 函数的时候被调用一次，如果调用了不止一次，你的程序会被判为 Wrong Answer [2]。
• 参数 $ I $ 是一个 $ 1 $ 到 $ N $ 的整数，不满足此条件时，会被判为 Wrong Answer [3]。
• 返回值是 $ S $ 的第 $ I $ 个字符。

评分的顺序

每个测试文件会包含多组测试数据，每组测试数据对应的字符串 $ S $ 的长度 $ N $ 是一样的。评测过程如下，如果一旦被判定为了 Wrong Answer，你的程序会立刻被终止。

• 在给出参数 $ N $，$ M $ 和 Get 的返回值的情况下，检查函数 Memory 的行为。也就是说对于满足 $ 0 \le M \le 2^{22} - 1 $ 的整数 $ M $，做如下操作：
• 对于每个在 <，>，[ 和 ] 的字符 $c$，会执行如下操作：把 $ N $ 和 $ M $ 作为参数传给 Memory 函数，当 Get 被调用的时候，把 $c$ 返回出去。用 $ m(M, c) $ 表示函数 Memory 的返回值。

• 上述操作会调用 $ 4 $ 次 Memory 函数，需要检测 Get 的调用是否一致。如果 Get 被调用了，那么这 $ 4 $ 次传给 Get 的参数 I 必须一样。如果 Get 没有被调用，那么这 $ 4 $ 次 Memory 的返回值必须要一样。不满足此条件时，会被判为 Wrong Answer [4]。当 Get 被调用的时候，我们令 $ i(M) $ 表示 $ I $ 的值（如果没有被调用 $i(M)=1$）。

• 对于每组数组里的字符串 $ S $，如下操作会被用来模拟课题描述

• 一开始 $ M = 0 $。
• 重复执行如下操作：
  • 令 $ c $ 是 $ S $ 的第 $ i(M) $ 个字符。
  • 把 $ M $ 换为 $ m(M, c) $。
  • $ M = -1 $ 或者 $ M = -2 $的情况下，跳出这个循环，进入下个流程。
  • 如果循环了超过 $ 15000 $ 次，你的程序会被判为 Wrong Answer [5]。

• 如果是以下某个情况，你的程序会被判为 Wrong Answer [6]。

  • $ S $ 是一个合法字符串，但是 $ M = -2 $。
  • $ S $ 不是一个合法字符串，但是 $ M = -1 $。

• 你的程序被认为是正确的。

编译与运行方法

「附加文件」中提供了 memory.h、grader-simple.c、grader-simple.cpp、grader-strict.c 和 grader-strict.cpp 五个文件。若你编写的程序名称为 memory.c 或 memory.cpp，请运行以下命令来编译：

• C 语言：
• gcc -std=c11 -O2 -o grader-simple grader-simple.c memory.c -lm
• gcc -std=c11 -O2 -o grader-strict grader-strict.c memory.c -lm
• C++ 语言：
• g++ -std=c++14 -O2 -o grader-simple grader-simple.cpp memory.cpp
• g++ -std=c++14 -O2 -o grader-strict grader-strict.cpp memory.cpp

当命令成功时，会产生一个可执行文件 grader-simple 或者 grader-strict。

注意实际评测时的程序与下发的样例评测程序并不相同。实际的 memory.h 函数实现将通过标准输入/输出与单独运行的交互器进行交互。

样例程序评测概要

grader-simple 不会模拟「评分的顺序」的第一步，但是会模拟课题的操作，具体可以参考「样例交互」。grader-strict 会严格按照「评分的顺序」执行。两者在输出上会有如下的不同：

• grader-simple 不会输出 Wrong Answer [4]，因为它并没有模拟这个操作
• grader-simple 和 grader-strict 不会输出 Wrong Answer [6]，但是会输出 $M$ 的值。

样例评测程序输入格式

grader-simple 和 grader-strict 将从标准输入读入以下数据。

• 第一行包含两个整数 $ N $ 和 $ Q $ ($0 \le Q \le 2^{31} - 1$)，表示字符串 $ S $ 的长度和测试数据组数。
• 接下来 $ Q $ 行，每行包含一个长度为 $ N $ 的字符串 $ S $。

样例评测程序输出格式

如果评测程序正常结束，grader-simple 和 grader-strict 将向标准输出输出以下信息。

• 程序正常结束的话，会输出 $ M $ 的值。
• 运行过程中被判为错误时，以 Wrong Answer [x] 的格式报告并退出。

样例评测输入

4 1
<>[]

样例交互

上述过程结束后 grader-simple 会输出 -1。

对于全部数据，满足 $ 1 \le |S| \le 100 $，字符串 $ S $ 仅由 <，>，[ 和 ] 组成。

本题共有 $ 6 $ 个子任务。每个子任务的分数和附加限制如下：