QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#100851#5119. Perfect Wordlgvc#AC ✓35ms8308kbC++231.2kb2023-04-28 13:17:432023-04-28 13:17:45

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-28 13:17:45]
  • 评测
  • 测评结果:AC
  • 用时:35ms
  • 内存:8308kb
  • [2023-04-28 13:17:43]
  • 提交

answer

//这回只花了114514min就打完了。
//真好。记得多手造几组。
#include <bits/stdc++.h>
#define int long long
#define MOD 1000000007
int T,as,pp[100009];
std::unordered_set<int> vq;
char s[100009];
std::vector<char> p[100009];
inline bool cmp(std::vector<char> a,std::vector<char> b) {
	return a.size()<b.size();
}
signed main(void) {
    //freopen("m.in","r",stdin);
    //freopen("m.out","w",stdout);
	scanf("%lld",&T);
	pp[0]=1;
	for(int i=1;i<=100000;i++) pp[i]=pp[i-1]*137%MOD;
	for(int i=1;i<=T;i++) {
		scanf("%s",s+1);
		p[i].push_back(0);
		for(int j=1;s[j];j++) {
			p[i].push_back(s[j]);
		}
	}
	std::sort(p+1,p+T+1,cmp);
	vq.insert(0);
	for(int i=1;i<=T;i++) {
		int vi=0;
		bool zz=0;
		for(int j=p[i].size()-1;j>1;j--) {
			vi+=pp[p[i].size()-1-j]*(p[i][j]-'a'+19)%MOD;
			vi%=MOD;
			if(vq.find(vi)==vq.end()) {
				zz=1;
				break;
			}
		} 
		if(zz) continue;
		vi+=pp[p[i].size()-2]*(p[i][1]-'a'+19)%MOD;
		vi%=MOD;
		int vt=0;
		for(int j=1;j<p[i].size()-1;j++) {
			vt=(vt*137+p[i][j]-'a'+19)%MOD;
		}
		if(vq.find(vt)!=vq.end()) {
			vq.insert(vi);
			as=std::max(as,(int)p[i].size()-1);
		}
	}
	printf("%lld",as);
    return 0;
}


Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 4ms
memory: 6692kb

input:

4
a
t
b
ab

output:

2

result:

ok 1 number(s): "2"

Test #2:

score: 0
Accepted
time: 5ms
memory: 6920kb

input:

310
a
aa
aaa
aaaa
aaaaa
aaaaaa
aaaaaaa
aaaaaaaa
aaaaaaaaa
aaaaaaaaaa
aaaaaaaaaaa
aaaaaaaaaaaa
aaaaaaaaaaaaa
aaaaaaaaaaaaaa
aaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaa...

output:

300

result:

ok 1 number(s): "300"

Test #3:

score: 0
Accepted
time: 8ms
memory: 6952kb

input:

4347
bbaaaab
aabab
bbaaaaababaaaba
aababaaaabbbabababaaaba
ababbabbbbbabbbabbab
bbbbbbb
bbbabbbabbabaab
aabbbbabbbbaa
aabaaabbbbbabaaababaa
aaabababba
aaababbaabab
abbababbabbab
bababaabbbbaaa
aaaaaabaaaababaa
ababaababba
babaababbbababaaab
bb
abbbaaaababa
b
ab
aaabbbbb
abaabaaaaababbbab
bbaaabaab
b...

output:

10

result:

ok 1 number(s): "10"

Test #4:

score: 0
Accepted
time: 4ms
memory: 6904kb

input:

5555
fdaaefdad
eacaeb
eeab
decaaddfdfffeb
ebcdeeceabfcded
aeeabcefdfdcb
abfdeeaac
daddadacebffcccb
abacccea
bcbec
ababfdaa
b
fbcccdbcdceafdefa
bdcd
a
ceaabbbae
e
eebeddcedecacafdc
ccdaebfd
ceeefb
baafbad
fadcaefbae
aad
a
dcdddedbdcdeabd
f
fdbccede
ebfb
efadfddddfed
fafefdfbdec
bcacbbafaaeddec
aebfec...

output:

5

result:

ok 1 number(s): "5"

Test #5:

score: 0
Accepted
time: 9ms
memory: 6956kb

input:

6249
a
a
aedbcbebea
bcebbaabeed
ebacbdbbaccdbbe
cceccaacb
ededaa
acdabaebaedab
bacdadacbec
ebbeaebabcebdd
bcec
adc
eeaaadba
eedabbaea
aadaadaecdcd
cdbdbddbababb
ea
ecccbebceddbae
ebaecdaebadad
ddccd
ebcebdcaecae
bccebebdcccbdbca
bccc
ebccdeeedbeea
aaedaeeaadbbbac
bbcee
caeccdbcbee
acbaabecccca
ea
cd...

output:

5

result:

ok 1 number(s): "5"

Test #6:

score: 0
Accepted
time: 2ms
memory: 6980kb

input:

3846
bcabccbcbcaabbaaaba
acabbbacccbbabbbc
ccabcbbacbc
bc
bbabaabcbcbbacbc
bccbcbbbbbcccbc
cabbcacaabcc
acaccccabbabbbbacaaabbaacb
bb
b
bcaccacbacabaaca
cbbacccbbcabcccbcac
bba
accbccacaaaccaccababba
aabcbabacabbaa
babcbbacaccababbbccbbb
acacaccbaccccbbbbcacbacba
aabaccaab
aacbcbbbbacabb
babaacccabc...

output:

6

result:

ok 1 number(s): "6"

Test #7:

score: 0
Accepted
time: 3ms
memory: 6924kb

input:

4166
dabdcacbdaeccdddbbdbaa
ebbe
aaebccdb
bbb
dbbcedbedcdcabebee
ceeeddaeeaabdc
bccdccecbcdbabbbea
bdbe
caebdbdddaaddeeacaacce
bcadededdebddcebdcee
ebddeeccaeacdab
ddedaccdbeeeacaeadcddcd
ca
ceddcedebcbbbaebdcdebcba
acaaaccaadb
da
edab
eadbaae
be
dabebdecdddbbcaaebcec
ababdbdcedcabbabdccea
eecdbdaad...

output:

5

result:

ok 1 number(s): "5"

Test #8:

score: 0
Accepted
time: 2ms
memory: 6908kb

input:

2777
cbccdbdbbeabbadfecfafebfaecdfefabccc
cd
b
eacefbcceada
ffebadacadfddeccadcabefcaeebaad
ebeccfdbfcadefcafefffbbddbedecab
dfbaaddcdafabbaafceadffefeddaaa
cdfdccedccddaceafccbfcaeebeda
cccbdebabcdaeebecbbbaaaebcbcfefbcda
cfefcabeaffcabdaabcbcfebfaeafeef
cdedd
debedaafaafbecfeedccaafeffbdbefedaa
fc...

output:

4

result:

ok 1 number(s): "4"

Test #9:

score: 0
Accepted
time: 8ms
memory: 6848kb

input:

3999
cbcbabccccbbcaaa
cbabaaaa
bbabbcbbbcbabcaaabc
aac
acaacbabcbabbbacabaccbaa
acbcbabcb
abbcbbbbcbaaacc
aabcaccbbbacbababcbaab
cbca
cca
bcabbccabbacaaacbaaaaaa
cabaaaabaabaaababbcc
ccacaaabacabacababcabbcab
babbbac
bbbbcaccbcaab
aca
bcbccccbaaccba
abcacaccccbbcbaccbacac
cacbaabaaabbca
bbcbbacb
cbb...

output:

6

result:

ok 1 number(s): "6"

Test #10:

score: 0
Accepted
time: 5ms
memory: 6948kb

input:

2083
edd
cdaacaeecadeadadd
cbbdccbbdbdddcbbbdb
ac
eeaeaaedbacdbeacbcbabbd
bebbcebbbddddcdddabebaed
daacaccebadbddbaedebdcaecbdee
ebeebeaecceebebdeeec
bbaedcaeadaebacadebacadbebabbaddcdceb
deeaaaecceaccebecccaececcdcdbbcbccdade
dbc
ebeabdeebbdbdcebdecbbdeccbabdcceacecbbc
bbbcadebadaaeeecbaacabedcbeae...

output:

4

result:

ok 1 number(s): "4"

Test #11:

score: 0
Accepted
time: 22ms
memory: 8044kb

input:

33333
knr
kmc
b
d
bmg
rej
fbn
ill
kdc
old
kpf
km
d
gjo
fod
ln
h
pdj
c
qfg
rci
o
eg
rp
n
eg
fig
ihn
h
om
nfg
cd
jhb
e
h
o
rpj
gd
h
lf
f
jb
h
qi
rq
n
km
o
ol
lpk
kp
gek
d
ebh
ch
ei
qm
hjh
eke
kb
djg
e
kl
ckk
m
k
fdr
ejr
m
q
md
bn
r
kf
gkn
nl
op
h
rcb
p
grr
cf
fq
dge
p
ioi
dk
f
pc
kdh
oqe
id
bfk
h
cpc
...

output:

3

result:

ok 1 number(s): "3"

Test #12:

score: 0
Accepted
time: 35ms
memory: 8308kb

input:

49999
cc
a
cb
a
d
c
cc
cc
bb
c
cc
d
dc
bd
cd
bb
bd
c
a
dc
d
cd
b
ab
dc
bb
cc
aa
c
c
ac
d
cb
d
c
a
b
b
ca
da
aa
d
bd
dc
c
b
bd
cc
a
a
cb
a
ad
d
a
bc
dc
a
bb
aa
b
bc
d
bb
c
cb
c
aa
ca
bd
da
ca
a
aa
b
ac
b
da
bd
cc
bb
a
aa
d
bc
ad
d
ca
a
c
b
ad
c
b
bd
c
b
a
d
ad
d
ac
c
cb
a
c
cc
bc
da
b
cd
cb
b
db
c
bb...

output:

2

result:

ok 1 number(s): "2"

Test #13:

score: 0
Accepted
time: 33ms
memory: 8276kb

input:

49999
hd
a
i
i
ig
gi
f
a
f
gh
ic
c
df
eg
cf
e
ei
e
ch
aa
c
dd
c
fh
fg
f
bh
eb
a
hf
e
fd
a
dg
ce
ed
i
h
c
h
g
b
g
e
gg
a
a
ee
a
hg
dh
db
gc
ci
ih
f
fc
ab
ce
f
e
b
i
c
fc
i
c
e
gh
f
de
h
e
cg
b
eb
b
ai
ei
fa
ci
i
e
ic
ab
c
de
gb
fi
dg
hh
ic
c
dc
hf
d
id
i
h
ab
c
h
bb
ca
e
g
g
gh
gh
i
ic
ie
f
b
bb
cd
c...

output:

2

result:

ok 1 number(s): "2"

Test #14:

score: 0
Accepted
time: 29ms
memory: 7820kb

input:

33333
eb
e
dg
b
d
b
bfa
fd
ga
g
ff
c
aeb
dd
ge
ace
cdc
f
gef
a
bdc
a
fbg
da
af
g
f
a
ab
bdd
cb
f
d
cdg
cc
e
eba
a
ef
af
fg
afb
da
fc
dfd
gcf
gd
e
c
b
b
gd
gcb
c
e
d
fe
bgc
f
gcc
bfe
ce
fc
d
deb
da
ffb
age
d
ebf
d
be
b
f
f
fda
d
cdd
d
da
bdb
acg
dcf
b
d
e
cea
e
ee
g
dab
fcd
ac
b
ac
gcg
f
e
ec
g
af
b
...

output:

3

result:

ok 1 number(s): "3"

Test #15:

score: 0
Accepted
time: 31ms
memory: 8256kb

input:

49999
ea
g
ig
ag
i
de
a
de
eg
e
e
db
g
h
a
dg
h
b
c
e
eh
c
e
i
gg
f
fd
g
fa
ed
ha
c
g
e
i
g
bd
c
f
gi
b
g
ca
fa
h
d
b
a
c
ed
i
b
g
h
i
i
ib
g
ie
e
bf
b
hg
a
ih
ei
cc
a
hi
g
f
dg
bd
c
ie
e
h
i
e
h
he
bb
ee
g
e
db
i
ii
i
f
eh
eg
i
h
dc
h
e
a
ga
c
h
d
d
hf
af
ef
a
h
f
d
hb
b
af
d
d
ic
e
a
cb
f
hi
id
g
...

output:

2

result:

ok 1 number(s): "2"