QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#687429#9522. A Simple String Problemucup-team5077AC ✓1350ms8988kbC++173.0kb2024-10-29 19:00:402024-11-10 22:37:36

Judging History

This is the latest submission verdict.

  • [2024-11-10 22:37:36]
  • 自动重测本题所有获得100分的提交记录
  • Verdict: AC
  • Time: 1350ms
  • Memory: 8988kb
  • [2024-11-10 22:36:11]
  • hack成功,自动添加数据
  • (/hack/1163)
  • [2024-11-06 21:49:00]
  • 自动重测本题所有获得100分的提交记录
  • Verdict: 100
  • Time: 1266ms
  • Memory: 8984kb
  • [2024-11-06 21:48:00]
  • hack成功,自动添加数据
  • (/hack/1142)
  • [2024-10-29 19:00:41]
  • Judged
  • Verdict: 100
  • Time: 1383ms
  • Memory: 9020kb
  • [2024-10-29 19:00:40]
  • Submitted

answer

#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double dou;
typedef pair<int,int> pii;
#define fi first
#define se second
#define mapa make_pair
typedef long double ld;
typedef unsigned long long ull;
#define ep emplace_back
template <typename T>inline void read(T &x){
	x=0;char c=getchar();bool f=0;
	for(;c<'0'||c>'9';c=getchar()) f|=(c=='-');
	for(;c>='0'&&c<='9';c=getchar())
	x=(x<<1)+(x<<3)+(c^48);
	x=(f?-x:x);
}
const int N=2e5+5;
int n;
char s[N], t[N];
int ans=0;
const int m1=998244353, m2=993244853;
struct hsh{
	int x, y;
	inline hsh operator +(const hsh &t){
		return (hsh){(x+t.x)%m1, (y+t.y)%m2};
	}
	inline hsh operator -(const hsh &t){
		return (hsh){(x-t.x+m1)%m1, (y-t.y+m2)%m2};
	}
	inline hsh operator *(const hsh &t){
		return (hsh){(int)((ll)x*t.x%m1), (int)((ll)y*t.y%m2)};
	}
	inline void operator +=(const hsh &t){
		x=(x+t.x)%m1, y=(y+t.y)%m2;
	}
	inline bool operator ==(const hsh &t){
		return x==t.x&&y==t.y;
	}
}hs[N], ht[N], pw[N]; 
const hsh bs=(hsh){137, 13331};
inline hsh gs(int l, int r){
	return hs[r]-hs[l-1]*pw[r-l+1];
}
inline hsh gt(int l, int r){
	return ht[r]-ht[l-1]*pw[r-l+1];
}
inline int lcs1(int x, int y){
	int l=1, r=x, mid, ret=0;
	while(l<=r){
		mid=(l+r)>>1;
		if(gt(x-mid+1, x)==gt(y-mid+1, y)) {ret=mid; l=mid+1;}
		else r=mid-1;
	}
	return ret;
}
inline int lcs2(int x, int y){
	int l=1, r=x, mid, ret=0;
	while(l<=r){
		mid=(l+r)>>1;
		if(gs(x-mid+1, x)==gt(y-mid+1, y)) {ret=mid; l=mid+1;}
		else r=mid-1;
	}
	return ret;
}
inline int lcs3(int x, int y){
	int l=1, r=x, mid, ret=0;
	while(l<=r){
		mid=(l+r)>>1;
		if(gs(x-mid+1, x)==gs(y-mid+1, y)) {ret=mid; l=mid+1;}
		else r=mid-1;
	}
	return ret;
}
inline int lcp1(int x, int y){
	int l=1, r=n-y+1, mid, ret=0;
	while(l<=r){
		mid=(l+r)>>1;
		if(gt(x, x+mid-1)==gt(y, y+mid-1)) {ret=mid; l=mid+1;}
		else r=mid-1;
	}
	return ret;
}
inline int lcp2(int x, int y){
	int l=1, r=n-y+1, mid, ret=0;
	while(l<=r){
		mid=(l+r)>>1;
		if(gs(x, x+mid-1)==gs(y, y+mid-1)) {ret=mid; l=mid+1;}
		else r=mid-1;
	}
	return ret;
}
inline void solve(){
	pw[0]=(hsh){1, 1};
	for(int i=1; i<=n; ++i) pw[i]=pw[i-1]*bs, hs[i]=hs[i-1]*bs+(hsh){s[i], s[i]}, ht[i]=ht[i-1]*bs+(hsh){t[i], t[i]};
	for(int i=1; i<n; ++i) if(s[i]==s[i+1]||s[i]==t[i+1]){
		ans=max(ans, 2); break;
	}
	for(int i=2; i<=n/2; ++i){
		bool flg=0;
		for(int j=1; j+i-1<=n; j+=i){
			// if(lcp2(j, j+i)+lcs3(j-1, j+i-1)>=i){
			// 	flg=1; break;
			// }
			int p2=j-lcs1(j-1, j+i-1);
			int p3=j+i+lcp1(j, j+i);
			int p1=p2-lcs2(p2-1, p2-1+i);
			if(p3-p1>=2*i) {flg=1; break;}
		}
		if(flg) ans=max(ans, 2*i);
	}
}
int main(){
	// freopen("D:\\nya\\acm\\A\\test.in","r",stdin);
	// freopen("D:\\nya\\acm\\A\\test.out","w",stdout);
	read(n); 
	scanf("%s", s+1);
	scanf("%s", t+2);
	s[n+1]='?'; t[1]='!';
	++n;
	solve();
	reverse(s+1, s+n+1);
	reverse(t+1, t+n+1);
	swap(s, t);
	solve();
	printf("%d\n", ans);
	return 0;
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 4312kb

input:

5
abcab
acabc

output:

6

result:

ok single line: '6'

Test #2:

score: 0
Accepted
time: 1ms
memory: 4224kb

input:

6
babbaa
babaaa

output:

6

result:

ok single line: '6'

Test #3:

score: 0
Accepted
time: 1ms
memory: 4212kb

input:

2
ne
fu

output:

0

result:

ok single line: '0'

Test #4:

score: 0
Accepted
time: 1ms
memory: 6096kb

input:

6
baabba
baabab

output:

4

result:

ok single line: '4'

Test #5:

score: 0
Accepted
time: 1ms
memory: 6100kb

input:

6
aaabba
aabbba

output:

2

result:

ok single line: '2'

Test #6:

score: 0
Accepted
time: 1ms
memory: 4172kb

input:

6
abaabb
bbbaba

output:

4

result:

ok single line: '4'

Test #7:

score: 0
Accepted
time: 1216ms
memory: 8948kb

input:

200000
wvblpxtatzytphgshchrevqqpnbljlorfoqubygysrivtemegmgrepemnlcbfqalpqqpvuockkbbvjnouhcerxqibevbipsxuscjejlcdtxoxipwrfrjwnriubvdgdgzlydwwiueovtrzljqxwfegejukncmahbcbsraxboukdesrzbwfvbpxpdntauidrybccwaocfwntohdkhxkfqhnoccyaylvvfebckmslrthubxrxvjoqcredanofbmgtsnswgszwhjckqeiddzvpnxphjkrwlsbthdvhzgn...

output:

200000

result:

ok single line: '200000'

Test #8:

score: 0
Accepted
time: 1215ms
memory: 8988kb

input:

199999
klwumjcvuqinrkcsyvgfixhwvrwbmazkclblcnlpyxtlmmpkllkpukmxaurpukvgibcsuigcoqnnreivrlrwfdqofqcwubpolnnxcansyaevdjvnhnzvjeoejktaodusltockhtuqrohqfsrezdzurowghmcateztzlltkzlqynxpgbqsvgqtpukmfgdxopynqaegmjxvjixyzjrhbgahxwkswgpanhrdgpyvtvcpsihdvmtixfskuiprfqrfknohthfblkzlrcyqewdycoljgwrhjkmoxqmtogmg...

output:

200000

result:

ok single line: '200000'

Test #9:

score: 0
Accepted
time: 1197ms
memory: 8956kb

input:

200000
yagcbqaxecsgdijvsdsqlemrrhyyuysvlbkkgultlmrapzokempkzmyyvgabgtqifgqhwyudzbkbjncsuixvyffpvtuczjakknocyskvqaohfvxomjhzirykpdwisgkmyomejaxbzamrnfcxjwjouskvjfuriurzknmhfvpvbdqunfckdmxhndvffhuybezncgohzwxvwfscltbhwvgvbrrejtuixsdwetkdxlogepphsvhyzybisqixsledftgegzbslkqsalhoifysrxsbjxvpojjxkqqoumlkj...

output:

114514

result:

ok single line: '114514'

Test #10:

score: 0
Accepted
time: 1350ms
memory: 8984kb

input:

200000
cbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbaca...

output:

0

result:

ok single line: '0'

Test #11:

score: 0
Accepted
time: 1246ms
memory: 8976kb

input:

200000
bbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbaba...

output:

150050

result:

ok single line: '150050'

Test #12:

score: 0
Accepted
time: 1168ms
memory: 8964kb

input:

200000
babababbaaaaaaabbbaaabbbbaaabbaaaabbaababbabbbbbababbbabbbaaabaaabaabbaabbaabbabbaaaaaababbbbbbaaaabaababbabaaabbbbbbabaaaabaaabaaaababaaabbbbbbaaabaabaaabbabbbabbbabaaaabbbbbbabbaabbaaaaaaaaabababbabbbbbaabaabaaabababbaabbbbbbabbaaaaababaabbaaaabbbbaaababbabbaabaabaabaaabbabaaaaabbabababbbaa...

output:

131072

result:

ok single line: '131072'

Test #13:

score: 0
Accepted
time: 1220ms
memory: 8896kb

input:

200000
rhqtphowacdrsxqisrqjhcsmxvwqtbmsvawxxxujgibnowkeyzhnjihsvsuklueukevgvlfqnrhalhglqlknerjwzizhxxszwjtnroubsjdhbnekbolwxaigyeypumuncdhmqqeljoyewehkhsqfoirchdnwazypwtefdyvtockpluejsftmffgbgdcotjnnkimawpflzwurdwrmpeudobzhpoyktufkgyvxpbfhuzswkrmnfzultfxdefoffvrfmuoufylyfvexnxgwgqfbiqvwpyenoqxncisuz...

output:

8

result:

ok single line: '8'

Test #14:

score: 0
Accepted
time: 1ms
memory: 4308kb

input:

10
aaabaabaaa
aabbbaaaba

output:

6

result:

ok single line: '6'

Test #15:

score: 0
Accepted
time: 1ms
memory: 6132kb

input:

17
ababbbaabbbaaaaba
abbabbbbbaabaabba

output:

10

result:

ok single line: '10'

Test #16:

score: 0
Accepted
time: 1ms
memory: 4208kb

input:

22
aaabbbaaaababbabbbbbbb
bbaabbbbbaaabbbabaaaaa

output:

8

result:

ok single line: '8'

Test #17:

score: 0
Accepted
time: 1ms
memory: 4252kb

input:

15
abaabaaaaabbbab
abbbabbbabababa

output:

8

result:

ok single line: '8'

Test #18:

score: 0
Accepted
time: 1ms
memory: 6088kb

input:

5
aabba
baaba

output:

6

result:

ok single line: '6'

Test #19:

score: 0
Accepted
time: 1ms
memory: 4292kb

input:

1
a
a

output:

2

result:

ok single line: '2'

Test #20:

score: 0
Accepted
time: 0ms
memory: 4304kb

input:

100
baabaaaabaabaabaaabaabbbabbbbbaababbabbbabbbbababaaabbabbaaaabbbaaabaabbbaaaaaababaababbbbbaaabbaabb
abbbbbbbbaaaaababbabbabbbbbaaaabbabbbaaaaabababbbabbababbbabbaabbabbabbbaaababbabbabbabbbabbbababaaa

output:

20

result:

ok single line: '20'

Test #21:

score: 0
Accepted
time: 0ms
memory: 6224kb

input:

32
babbbbbabbababaabbbaaaaabbaababa
abbbaaababaabababbaaabaaabbaaaab

output:

18

result:

ok single line: '18'

Extra Test:

score: 0
Extra Test Passed