题目大意

有一个隐藏的字符串 $S$，你每天可以询问 $S$ 中的一个字符并将一个小于 $2^{22}$ 的非负整数传给下一天。

你需要在 $15000$ 天内判断出此字符串是否合法。

题目思路

我们可以先找到一个左括号，然后去寻找和它匹配的右括号。

所以可以从此左括号开始不断往后找，使用一个变量 $c$，遇到左括号就把 $c$ 加一 ，否则就减一。当 $c$ 第一次为 $-1$ 时，此位置的括号即为与它匹配的括号。 匹配完之后再带回去一个 $b$ 代表此右括号的位置。之后从 $b + 1$ 继续往后找即可。

解决此过程需要储存当前位置 $a$，上文的 $b$，上文的 $c$，和一个状态 $d$。

状态 $d$ 有 $4$ 种情况，分别是寻找左括号，往前找与之前的左括号匹配的括号，匹配左括号中和匹配右括号中。

传递的数最大为 $4 \times 10^6$，符合要求。

参考代码

#include<bits/stdc++.h>
using namespace std;
char Get(int I);
int Memory(int N,int M){
	int a=M%100,b=M/100%100,c=M/10000%100,d=M/1000000;
	if(a>=N)return 0;
	char ch=Get(a+1);
	if(!d)return ((a+1==N||ch=='>'||ch==']')?-2:2000001+a+1000000*(ch=='<'));
	else if(d==1){
		c+=((ch==']'||ch=='>')?1:-1);
		return (c==-1?(b==N-1?-2:2000001+b+1000000*(ch=='<')):(a==0?(b==N-1?-1:b+1):a-1+b*100+c*10000+1000000));
	}
	else if(d==2)return (ch==']'?a*101+1000000:((a==N-1||ch=='>')?-2:2000001+a+1000000*(ch=='<')));
	else return (ch=='>'?a*101+1000000:((a==N-1||ch==']')?-2:2000001+a+1000000*(ch=='<')));
}