QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#418386#5119. Perfect Wordxqbf#AC ✓72ms11692kbC++141.4kb2024-05-23 13:30:432024-05-23 13:30:44

Judging History

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

  • [2024-05-23 13:30:44]
  • 评测
  • 测评结果:AC
  • 用时:72ms
  • 内存:11692kb
  • [2024-05-23 13:30:43]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

const int threhold = 2 * sqrt(100000);

struct Hashing{
	int Mod(int x){ return x >= mod ? x - mod : x; }
	int mul(int x, int y){ return 1ll * x * y % mod; }
	int mod, P, C;
	multiset <int> S;
	void init(int mod_, int P_, int C_){
		mod = mod_, P = P_, C = C_;
	}
	int gethsh(string st){
		int len = st.length(), hsh = 0;
		for (int i = 0; i < len; i++)
			hsh = Mod(mul(hsh, P) + st[i] + C);
		return hsh;
	}
	void insert(string st){
		S.insert(gethsh(st));
	}
	bool findin(string st){
		return S.find(gethsh(st)) != S.end();
	}
	bool findin(int hsh){
		return S.find(hsh) != S.end();
	}
	bool check(string st){
		int len = st.length();
		for (int i = 0; i < len; i++){
			int hsh = 0;
			for (int j = i; j < len; j++){
				hsh = Mod(mul(hsh, P) + st[j] + C);
				if (!findin(hsh)) 
					return false;
			}
		}
		return true;
	}
} H1, H2;

bool check(string st){
	return H1.check(st) && H2.check(st);
}

string st[100500];
int n;

int main(){
	H1.init(1e9 + 7, 13337, 123), H2.init(998244353, 13333337, 0);
	ios :: sync_with_stdio(false), cin.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> st[i], H1.insert(st[i]), H2.insert(st[i]);
	int ans = 0;
	for (int i = 1; i <= n; i++)
		if (st[i].length() <= threhold)
			if (check(st[i])) ans = max(ans, (int) st[i].length());
	cout << ans << endl;
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 6704kb

input:

4
a
t
b
ab

output:

2

result:

ok 1 number(s): "2"

Test #2:

score: 0
Accepted
time: 72ms
memory: 6828kb

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: 2ms
memory: 7404kb

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: 2ms
memory: 7272kb

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: 6ms
memory: 7368kb

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: 4ms
memory: 7148kb

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: 4ms
memory: 7172kb

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: 7300kb

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: 4ms
memory: 7216kb

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: 3ms
memory: 7264kb

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: 32ms
memory: 9832kb

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: 21ms
memory: 11692kb

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: 26ms
memory: 11432kb

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: 25ms
memory: 9832kb

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: 26ms
memory: 11456kb

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"