记录编号	76787	评测结果	AAAAAAAAAA
题目名称	解密牛语	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.222 s
提交时间	2013-10-31 15:08:05	内存使用	0.38 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<iomanip>
#include<map>
#include<set>
using namespace std;
const int SIZEPART=13;
string ori_st;
string goal_st="\0";
int num_COW=0;
bool pair_exi[256][256]={0};
void output(string &st){
	int i;
	for(i=0;i<st.size();i++){
		if(st[i]>='A') cout<<st[i]<<" ";
		else cout<<(int)st[i]<<" ";
	}
	cout<<endl;
}
bool is_spt(char ch){
	if(ch=='C'||ch=='O'||ch=='W') return true;
	return false;
}
set<int> hash;
int BKDRhash(string &str){
	int i;
	int seed=131,ans=0;
	for(i=0;i<str.size();i++){
		ans+=ans*seed+(int)str[i];
	}
	return ans&0x7fffffff;
}
void erase_fix(void){//删除相同前后缀
	int i,j;
	i=0,j=0;
	while(ori_st[i]==goal_st[j]){
		ori_st.erase(i,1),goal_st.erase(j,1);
		i=0,j=0;
	}
	i=ori_st.size()-1,j=goal_st.size()-1;
	while(ori_st[i]==goal_st[j]){
		ori_st.erase(i,1),goal_st.erase(j,1);
		i=ori_st.size()-1,j=goal_st.size()-1;
	}
}
int appear_time(string &goal,string &st,int a,int len){
	int i,j;
	int sum=0;
	for(i=0;i<goal.size();i++){
		j=0;
		while(i+j<goal.size()&&j<len&&goal[i+j]==st[a+j]) j++;
		if(j==len) sum++;
	}
	return sum;
}
int appear_pos(string &goal,string &st,int a,int len){
	int i,j;
	int sum=0;
	for(i=0;i<goal.size();i++){
		j=0;
		while(i+j<goal.size()&&j<len&&goal[i+j]==st[a+j]) j++;
		if(j==len) return i;
	}
	return -1;
}
char tot=(char)1;
bool shorten_rp(string &ori_st,string &goal_st){
	int i,j;
	int temp,sp;
	string str;
	i=1;
	while(i<ori_st.size()){
		if(is_spt(ori_st[i-1])&&!is_spt(ori_st[i])){
			j=i;
			while(j+1<ori_st.size()&&!is_spt(ori_st[j+1])) j++;
			temp=appear_time(goal_st,ori_st,i,j-i+1);
			if(temp==0) return false;
			if(temp==1){
				str="\0";
				str+=tot;
				sp=appear_pos(goal_st,ori_st,i,j-i+1);
				goal_st=goal_st.replace(sp,j-i+1,str);
				ori_st=ori_st.replace(i,j-i+1,str);
				tot++;
			}
			i++;
		}
		i++;
	}
	return true;
}
bool all_pair_exi(string &st){
	int i;
	for(i=0;i+1<st.size();i++){
		if(!is_spt(st[i])&&!is_spt(st[i+1])){
			if(!pair_exi[(int)st[i]][(int)st[i+1]]) return false;
		}
	}
	return true;
}
void get_exi(void){
	int i;
	for(i=0;i+1<goal_st.size();i++){
		if(!is_spt(goal_st[i])&&!is_spt(goal_st[i+1])){
			pair_exi[(int)goal_st[i]][(int)goal_st[i+1]]=true;
		}
	}
}
string exchange(string &st,int a,int b,int c){
	string ans="\0";
	int i;
	for(i=0;i<a;i++) ans+=st[i];
	for(i=b+1;i<c;i++) ans+=st[i];
	for(i=a+1;i<b;i++) ans+=st[i];
	for(i=c+1;i<st.size();i++) ans+=st[i];
	return ans;
}
bool same_fix(string &st){
	int i,j;
	i=0,j=0;
	while(!is_spt(st[i])){
		if(st[i]!=goal_st[j]) return false;
		i++,j++;
	}
	i=st.size()-1,j=goal_st.size()-1;
	while(!is_spt(st[i])){
		if(st[i]!=goal_st[j]) return false;
		i--,j--;
	}
	return true;
}
bool already_searched(string &str){
	return hash.find(BKDRhash(str))!=hash.end();
}
int max_dep=0;
bool DFS(string st,int deep){
	if(deep==num_COW){
		return st==goal_st;
	}
	if(!all_pair_exi(st)) return false;
	int i,j,k;
	if(!same_fix(st)) return false;
	for(i=0;i<st.size();i++){
		if(is_spt(st[i])){
			if(st[i]!='C') return false;
			break;
		}
	}
	for(i=st.size()-1;i>=0;i--){
		if(is_spt(st[i])){
			if(st[i]!='W') return false;
			break;
		}
	}
	if(already_searched(st)) return false;
	hash.insert(BKDRhash(st));
	for(j=0;j<st.size();j++){
		if(st[j]!='O') continue;
		for(i=0;i<j;i++){
			if(st[i]!='C') continue;
			for(k=j+1;k<st.size();k++){
				if(st[k]!='W') continue;
				if(DFS(exchange(st,i,j,k),deep+1)) return true;
			}
		}
	}
	return false;
}
bool is_legal(){
	int rightlis[256]={0};
	int nowlis[256]={0};
	num_COW=ori_st.size()-goal_st.size();
	if(num_COW%3) return false;
	num_COW/=3;
	int i;
	for(i=0;i<(int)goal_st.size();i++) rightlis[(int)goal_st[i]]++;
	for(i=0;i<(int)ori_st.size();i++) nowlis[(int)ori_st[i]]++;
	for(i=(int)'A';i<=(int)'z';i++){
		if('Z'<i&&i<'a') continue;
		if(is_spt((char)i)) continue;
		if(rightlis[i]!=nowlis[i]) return false;
	}
	if(nowlis[(int)'C']==nowlis[(int)'O']&&nowlis[(int)'O']==nowlis[(int)'W']&&nowlis[(int)'C']==num_COW) return true;
	return false;
}
int main(){
	freopen("cryptcow.in","r",stdin);
	freopen("cryptcow.out","w",stdout);
	goal_st+="Begin the Escape ex";
	goal_st+="ecution at the Break of Dawn";
	getline(cin,ori_st);
	if(!is_legal()){
		printf("0 0\n");
		return 0;
	}
	if(num_COW==0){
		printf("1 0\n");
		return 0;
	}
	erase_fix();
	if(ori_st[0]!='C'||ori_st[ori_st.size()-1]!='W'){
		printf("0 0\n");
		return 0;
	}
	if(!shorten_rp(ori_st,goal_st)){
		printf("0 0\n");
		return 0;
	}
	shorten_rp(ori_st,goal_st);
	get_exi();
	if(DFS(ori_st,0)){
		printf("1 %d\n",num_COW);
		return 0;
	}
	printf("0 0\n");
	return 0;
}