I got a lots of WA a on this easy looking problem ~x(
but cann't find the cause..
may be some of u can help me to find out the cause.
here is my code and some test cases...
Code: Select all
#include <vector>
#include <string>
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
using namespace std;
#define All(X) X.begin(),X.end()
#define co continue
#define re return
#define ox 2147483647
struct ToCh{
int f;
char tc[28];
};
struct inCh{
int i;
char a, b;
};
bool comp(inCh a,inCh b){
re a.i<b.i;
}
int main(){
char word[110],toch[28],x[5],y[5];
int i,j,n,siz,next,k,cas=1,l;
vector<ToCh>update;
vector<inCh>temp;
inCh R;
ToCh T;
//freopen("11058.txt","r",stdin);
//freopen("11058.out","w",stdout);
while(scanf("%s",word)==1){
for(i=0;i<26;i++){
scanf("%s",x);
toch[i]=x[0];
}
toch[i]='\0';
scanf("%d",&n);
update.clear();
temp.clear();
siz=0;
for(j=0;j<n;j++){
scanf("%d %s %s",&i, x,y);
R.i=i;R.a=x[0];R.b=y[0];
temp.push_back(R);
}
sort(All(temp),comp); //this sort may be unnecessay, but i consider it to sure
k=-1;
for(l=0;l<n;l++){
//scanf("%d %s %s",&i, x,y);
i=temp[l].i;
x[0]=temp[l].a;
y[0]=temp[l].b;
if(i!=k){
k=T.f=i;
for(j=0;j<26;j++){
T.tc[j]=-1;
}
T.tc[x[0]-'a']=y[0];
update.push_back(T);
siz++;
}else{
update[siz-1].tc[x[0]-'a']=y[0];
}
}
if(k!=-1)
next=update[0].f;
else next=-1;
k=0;
for(i=0;word[i]!='\0';i++){
if(i==next && k<siz){
for(j=0;j<26;j++){
x[0]=update[k].tc[j];
if(x[0]!=-1){
toch[j]=x[0];
}
}
k++;
next=update[k].f;
}
word[i]=toch[word[i]-'a'];
}
printf("Case #%d: The encoding string is %s.\n\n",cas++,word);
}
return 0;
}
I test this with the following inputs
Code: Select all
aaab
b
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
5
0 a a
1 a b
2 a c
3 b d
4 x y
abcd
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
5
0 a z
1 a y
2 a x
3 a w
4 x y
aaaa
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
5
0 a z
1 a y
2 a x
3 a w
4 x y
baba
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
4
0 b a
1 a b
1 b x
2 a x
aaaaaa
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
2
2 a b
4 a a
ufrn
t
o
w
k
q
z
f
n
y
i
c
m
s
j
n
r
g
l
d
s
u
s
g
y
e
u
14
0 q t
0 j f
1 v d
1 r o
1 f d
1 r o
1 f a
2 e p
2 r w
2 v e
2 f x
3 y p
3 t m
3 u k
abcdisdbcaront
a
b
c
d
e
f
g
h
i
j
k
l
m
n
o
p
q
r
s
t
u
v
w
x
y
z
0
abcdisdbcaront
a
b
c
d
e
f
g
h
i
j
k
l
m
n
o
p
q
r
s
t
u
v
w
x
y
z
7
0 a x
0 a w
0 b h
1 d t
2 c a
4 c e
10 t g
the output of this code is:
Code: Select all
Case #1: The encoding string is abcd.
Case #2: The encoding string is zaaa.
Case #3: The encoding string is zyxw.
Case #4: The encoding string is abxx.
Case #5: The encoding string is aabbaa.
Case #6: The encoding string is uawj.
Case #7: The encoding string is abcdisdbcaront.
Case #8: The encoding string is whatisthewrong.