QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#665564#5119. Perfect WordRepeater#AC ✓9ms6276kbC++201.9kb2024-10-22 14:05:562024-10-22 14:06:02

Judging History

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

  • [2024-10-22 14:06:02]
  • 评测
  • 测评结果:AC
  • 用时:9ms
  • 内存:6276kb
  • [2024-10-22 14:05:56]
  • 提交

answer

#include<iostream>
using namespace std;
#include<vector>
#include<string>
#include<algorithm>
#include<map>

const int base[2] = {133, 331};
const int mod[2] = {(int)1e9 + 463, (int)1e9 + 469};

using i64 = long long;

const int N = 1e5 + 1;
vector<i64> power[2];

void init(){
	for(int i = 0; i < 2; ++i){
		power[i].assign(N, 1);
		for(int j = 1; j < N; ++j){
			power[i][j] = power[i][j - 1] * base[i] % mod[i];
		}
	}
	return;
}

pair<int, int> getHash(string s){
	pair<int, int> ans;
	for(int i = 0; i < s.size(); ++i){
		ans.first = (1LL * ans.first * base[0] + s[i]) % mod[0];
		ans.second = (1LL * ans.second * base[1] + s[i]) % mod[1];
	}
	return ans;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	init();

	int n = 0;
	cin >> n;

	map<pair<int, int>, bool> mp;

	vector<string> s(n);
	for(int i = 0; i < n; ++i){
		cin >> s[i];
	}

	sort(s.begin(), s.end(),
		[&](const string& a, const string& b) {return a.size() < b.size();});

	int answer = 0;
	for(int i = 0; i < n; ++i){
		if(s[i].size() == 1){
			mp[pair<int, int>(s[i][0], s[i][0])] = true;
		}
		else{
			int m = s[i].size();

			pair<int, int> ans;
	        for(int j = 0; j < m - 1; ++j){
		        ans.first = (1LL * ans.first * base[0] + s[i][j]) % mod[0];
				ans.second = (1LL * ans.second * base[1] + s[i][j]) % mod[1];
			}

			int cnt = 0;

			if(mp.find(ans) != mp.end()) cnt++;

			ans.first = (1LL * ans.first * base[0] + s[i][m - 1]) % mod[0];
			ans.second = (1LL * ans.second * base[1] + s[i][m - 1]) % mod[1];

			pair<int, int> a = ans;
			a.first = (a.first - s[i][0] * power[0][m - 1] % mod[0] + mod[0]) % mod[0];
			a.second = (a.second - s[i][0] * power[1][m - 1] % mod[1] + mod[1]) % mod[1]; 

			if(mp.find(a) != mp.end()) ++cnt;

			if(cnt == 2){
				mp[ans] = true;
				answer = max(answer, m);
			}  
		}
	}

	cout << answer << "\n";

	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 4688kb

input:

4
a
t
b
ab

output:

2

result:

ok 1 number(s): "2"

Test #2:

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

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

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

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

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: 0ms
memory: 4964kb

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

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: 0ms
memory: 5008kb

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

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: 0ms
memory: 4908kb

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

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

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: 5ms
memory: 6244kb

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: 9ms
memory: 5744kb

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: 5ms
memory: 6204kb

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"