记录编号	98095	评测结果	AAAAAAAAAA
题目名称	复原序列	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	1.734 s
提交时间	2014-04-21 17:52:26	内存使用	15.88 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cmath>
using namespace std;
const int SIZEN=20010,SIZESTEP=200;
string A,B;
vector<int> block;
int M;
bool stepf[SIZESTEP][SIZEN]={0};
vector<int> tpable[2];
bool c[SIZESTEP][SIZEN][2]={0};//0储存v-1是否可行,1储存v是否可行
bool visit[SIZESTEP][SIZEN]={0};
bool ansable[SIZEN][2]={0};
//1是+,0是-
vector<int> reach[SIZEN];
bool tpf[2][SIZEN];
int BOT;
bool solution=false;
void getgraph(bool f[SIZEN],int bot,int n){
	memcpy(tpf[0],f,sizeof(tpf[0]));
	tpable[0].clear();
	memset(c,0,sizeof(c));
	for(int i=0;i<B.size();i++) if(f[i]) tpable[0].push_back(i); 
	for(int i=1;i<=n;i++){
		int k=(i&1);
		memset(tpf[k],0,sizeof(tpf[0]));
		tpable[k].clear();
		for(int t=0;t<tpable[k^1].size();t++){
			for(int j=tpable[k^1][t];j<=tpable[k^1][t]+1;j++){
				if(tpf[k][j]) continue;
				if(B[j]=='+'){
					if(A[bot+i]=='+'||A[bot+i]=='?'){
						if(tpf[k^1][j-1]){
							c[i][j][0]=true;
							tpf[k][j]=true;
						}
					}
					else tpf[k][j]=0;
				}
				else if(B[j]=='*'){
					if(A[bot+i]=='-'||A[bot+i]=='?'){
						if(tpf[k^1][j-1]){
							c[i][j][0]=true;
							tpf[k][j]=true;
						}
						if(tpf[k^1][j]){
							c[i][j][1]=true;
							tpf[k][j]=true;
						}
					}
					else tpf[k][j]=0;
				}
				if(tpf[k][j]) tpable[k].push_back(j);
			}
		}
	}
}
void work(void){
	if(!solution){
		printf("No Solution\n");
		return;
	}
	BOT=A.size();
	ansable[A.size()-1][0]=true;
	reach[A.size()-1].push_back(B.size()-1);
	memset(visit,0,sizeof(visit));
	for(int i=A.size()-1;i>0;i--){
		if(i<=BOT){
			BOT=((i-1)/M)*M;
			getgraph(stepf[(i-1)/M],BOT,i-BOT);
			memset(visit,0,sizeof(visit));
		}
		for(int t=0;t<reach[i].size();t++){
			int j=reach[i][t];//第i层,B[j]能到达
			if(visit[i-BOT][j]) continue;
			visit[i-BOT][j]=true;
			for(int r=0;r<=1;r++){
				if(c[i-BOT][j][r]){
					char ch=B[j+(r-1)];
					if(ch=='+') ansable[i-1][1]=true;
					else if(ch=='*') ansable[i-1][0]=true;
					reach[i-1].push_back(j+(r-1));
				}
			}
		}
	}
	for(int i=1;i<A.size()-1;i++){
		if(ansable[i][0]&&ansable[i][1]) printf("?");
		else if(ansable[i][0]) printf("-");
		else if(ansable[i][1]) printf("+");
	}
	printf("\n");
}
void getable(void){
	memset(tpf[0],0,sizeof(tpf[0]));
	tpf[0][0]=true;
	memcpy(stepf[0],tpf[0],sizeof(tpf[0]));
	tpable[0].push_back(0);
	for(int i=1;i<A.size();i++){
		int k=(i&1);
		memset(tpf[k],0,sizeof(tpf[0]));
		tpable[k].clear();
		for(int t=0;t<tpable[k^1].size();t++){
			for(int j=tpable[k^1][t];j<=tpable[k^1][t]+1;j++){
				if(tpf[k][j]) continue;
				if(B[j]=='+'){
					if(A[i]=='+'||A[i]=='?') tpf[k][j]=tpf[k^1][j-1];
					else tpf[k][j]=0;
				}
				else if(B[j]=='*'){
					if(A[i]=='-'||A[i]=='?') tpf[k][j]=(tpf[k^1][j-1]||tpf[k^1][j]);
					else tpf[k][j]=0;
				}
				if(tpf[k][j]) tpable[k].push_back(j);
				if(i==A.size()-1&&j==B.size()-1) solution=tpf[k][j];
			}
		}
		if(i%M==0) memcpy(stepf[i/M],tpf[k],sizeof(tpf[0]));
	}
}
void init(void){
	cin>>A;
	if(M<1) M=1;
	int x;
	while(scanf("%d",&x)!=EOF) block.push_back(x);
	A="-"+A+"-";
	B="*";
	for(int i=0;i<block.size();i++){
		for(int j=0;j<block[i];j++) B+="+";
		B+="*";
	}
	M=sqrt(A.size()+0.0);
}
int main(){
	freopen("recover.in","r",stdin);
	freopen("recover.out","w",stdout);
	init();
	getable();
	work();
	return 0;
}