QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #445359 | #8521. Pattern Search II | ucup-team1134# | WA | 1423ms | 7936kb | C++23 | 4.7kb | 2024-06-16 01:34:06 | 2024-06-16 01:34:06 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef __int128_t ll;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define mp make_pair
#define si(x) int(x.size())
const int mod=998244353,MAX=150002,INF=15<<26;
int dpB[MAX],dpA[MAX];
int main(){
std::ifstream in("text.txt");
std::cin.rdbuf(in.rdbuf());
cin.tie(0);
ios::sync_with_stdio(false);
vector<string> SS(31);
SS[0]="b";
SS[1]="a";
for(int i=2;i<=30;i++){
SS[i]=SS[i-1]+SS[i-2];
//cout<<i<<" "<<si(SS[i])<<endl;
}
string B=SS[13],A=SS[14];
vector<string> TT(31);
TT[13]='B';
TT[14]='A';
for(int i=15;i<=30;i++) TT[i]=TT[i-1]+TT[i-2];
string S;cin>>S;
string T=TT[27]+TT[27];
for(int i=0;i<si(S);i++){
int now=i;
for(char c:B){
if(now<si(S)&&c==S[now]) now++;
}
dpB[i]=now;
}
for(int i=0;i<si(S);i++){
int now=i;
for(char c:A){
if(now<si(S)&&c==S[now]) now++;
}
dpA[i]=now;
}
int ans=INF;
for(int s=0;s<si(T);s++){
if(T[s]=='B'){
for(int j=0;j<si(B);j++){
int now=0,cn=0;
for(int i=j;i<si(B);i++){
if(now<si(S)&&B[i]==S[now]) now++;
if(now==si(S)){
chmin(ans,i-j+1);
break;
}
}
if(now==si(S)) continue;
cn=si(B)-j;
for(int x=s+1;x<si(T);x++){
if(T[x]=='A'){
if(dpA[now]<si(S)) now=dpA[now];
else{
for(int i=0;i<si(A);i++){
if(now<si(S)&&A[i]==S[now]) now++;
if(now==si(S)){
chmin(ans,cn+(i+1));
break;
}
}
break;
}
cn+=si(A);
}else{
if(dpB[now]<si(S)) now=dpB[now];
else{
for(int i=0;i<si(B);i++){
if(now<si(S)&&B[i]==S[now]) now++;
if(now==si(S)){
chmin(ans,cn+(i+1));
break;
}
}
break;
}
cn+=si(B);
}
}
}
}else{
for(int j=0;j<si(A);j++){
int now=0,cn=0;
for(int i=j;i<si(A);i++){
if(now<si(S)&&A[i]==S[now]) now++;
if(now==si(S)){
chmin(ans,i-j+1);
break;
}
}
if(now==si(S)) continue;
cn=si(A)-j;
for(int x=s+1;x<si(T);x++){
if(T[x]=='A'){
if(dpA[now]<si(S)) now=dpA[now];
else{
for(int i=0;i<si(A);i++){
if(now<si(S)&&A[i]==S[now]) now++;
if(now==si(S)){
chmin(ans,cn+(i+1));
break;
}
}
break;
}
cn+=si(A);
}else{
if(dpB[now]<si(S)) now=dpB[now];
else{
for(int i=0;i<si(B);i++){
if(now<si(S)&&B[i]==S[now]) now++;
if(now==si(S)){
chmin(ans,cn+(i+1));
break;
}
}
break;
}
cn+=si(B);
}
}
}
}
}
cout<<ans<<endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 6ms
memory: 6596kb
input:
aabbaab
output:
8
result:
ok 1 number(s): "8"
Test #2:
score: 0
Accepted
time: 3ms
memory: 6596kb
input:
a
output:
1
result:
ok 1 number(s): "1"
Test #3:
score: 0
Accepted
time: 4ms
memory: 6672kb
input:
b
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 5ms
memory: 6596kb
input:
aa
output:
2
result:
ok 1 number(s): "2"
Test #5:
score: 0
Accepted
time: 2ms
memory: 6564kb
input:
bb
output:
3
result:
ok 1 number(s): "3"
Test #6:
score: 0
Accepted
time: 5ms
memory: 6612kb
input:
ab
output:
2
result:
ok 1 number(s): "2"
Test #7:
score: 0
Accepted
time: 2ms
memory: 6608kb
input:
ba
output:
2
result:
ok 1 number(s): "2"
Test #8:
score: 0
Accepted
time: 8ms
memory: 6748kb
input:
bbba
output:
7
result:
ok 1 number(s): "7"
Test #9:
score: 0
Accepted
time: 12ms
memory: 6740kb
input:
abbbbbbbab
output:
20
result:
ok 1 number(s): "20"
Test #10:
score: 0
Accepted
time: 28ms
memory: 6580kb
input:
abbbbabbbabbbabbabaabbabb
output:
43
result:
ok 1 number(s): "43"
Test #11:
score: 0
Accepted
time: 82ms
memory: 6628kb
input:
bbbaabaabbbaabababbbabaaabaaabbbaaaabaabaaaaabbabbbababbabaaba
output:
94
result:
ok 1 number(s): "94"
Test #12:
score: 0
Accepted
time: 203ms
memory: 6596kb
input:
ababaaabbaaaabaaaaabbabbbababaabaabbabbabaaaabbbabbaaaabaaaabbbabaaaaabbbbbbbbaabaabaabbbbbbabbaabaaaabbbabbbaaabaaabaababaabbbbbbbbaabababaabbaabbbaaaaabb
output:
245
result:
ok 1 number(s): "245"
Test #13:
score: 0
Accepted
time: 462ms
memory: 6572kb
input:
aaaabbbbaaaaababababaaabbbbbbababbaaaaabaaaaaabababbaabbbabbabbbbabbbabaabaaaabababaabbbaaaaabbbabaabaaaababaabbaaabbbaaaabbbaabbaaabbabbbabbabbaababbbbabbbbbbabbaaabbaabbbbbbabababbaaababbaaaaaaabaabbaabbabbbaaaaaaaaaababbaaaabaabbbabbbaabbabbbaabaaaaaabaababaaaababaaaaaababbaaaaaabaabbaabbbbbbaaba...
output:
625
result:
ok 1 number(s): "625"
Test #14:
score: 0
Accepted
time: 405ms
memory: 6568kb
input:
aabaababbbbbbbbaabaaaaaabbbaababbabbabbaabbaaaaabaaaabbbbababbaabaaaaaabbbbabbbbbbbabbbaababbbbbbabaaababbaabaaaabbaababbbaaabbabababbbbbabbbaaaaaabbaabbbbabbabbaaaaaabababbabbbbabaabbbbbbbbaaabababbbbbbbaaababbbbbbabbbbabbaaabbbbaaabaaabbaabaabbaaaabababbabbabababbbaabbbbbabaaabbbabbbababbaababbbba...
output:
1608
result:
ok 1 number(s): "1608"
Test #15:
score: 0
Accepted
time: 427ms
memory: 6812kb
input:
aaababbbabbaabbbababbaaababaabbbbbabbbabbbabbabbaabbabbabaaabaabbbbbabababbbabaaaabaaababbabaaaabababbaabbaaaaaababaabababbbaaaabbababbbaaaaabababbaaaaabaabbbbbbaabaaaabbbaaababaabbbabaabaaababbbaaaaaabbbbbbbabbbabbaaaababbababaababaabbbbbaaaaabbababbbaabaabbabbaabbbbabaaabbababaaaabbbabaaabaabbbbab...
output:
3954
result:
ok 1 number(s): "3954"
Test #16:
score: 0
Accepted
time: 435ms
memory: 6704kb
input:
aaabbbbabaaabbabbaabbabbbbbbbaaabbaaaaabbbbbaaaabbbaaabbabbaabaabbbaabaababaabbbababbbbbbabbababbbbabaaababbbaaabbabbbaabbbbbbbbbbabbbbbabbabbbbabbbbbbbaabaaaaaabbbaaabaabaaaaabbabbaaabbababaaaaaababbbabaabbbaabaaabaabbabaaaaababaaabbaabaababbaaabaabbaabbbbaababbaabaaabababbbbbabbbbababbbbbbaabbabab...
output:
10033
result:
ok 1 number(s): "10033"
Test #17:
score: 0
Accepted
time: 492ms
memory: 6800kb
input:
aabbbbbabababbbababaaabaabbbbbbaaababaabaababbbbbaabaabababaabbbbbbaabbbababbbbbbbbbbabababbabbaaaabaaaaabbabbbabbaaaaababababaaabbbbbbbabbbbbbbbaaabbbaaababbaaaaaabaabbaababbbabaaabbbaabbabababbaaaababbbabbbabaaaaabbbabbbabbaaaabababbbbbbaabbbaaaabbabbabbabbbbbbbaabbbaabbbbabbbaabbbbbbabaaaabbaaabb...
output:
24882
result:
ok 1 number(s): "24882"
Test #18:
score: 0
Accepted
time: 668ms
memory: 7072kb
input:
bbabaaababbabbbbbbababaababaaabababaabbbaabbbabbababbbbbabbbbaaabbbbaaaaabbaaabbbabbbbaabaabbaaaabaababbbababbbbaaaaabaabaababbbbbabbbabbaaabbabbbbaabbabababababababaabbaabbaabbabaaaabaaabbbbbababbbbaaaaabaababbbbabaaaabababaaabaaaabbbbabbbbabaaaaaababbbbabaaabaaaabaaabaabaabaabaaabbabbbbabbababaaab...
output:
62283
result:
ok 1 number(s): "62283"
Test #19:
score: 0
Accepted
time: 1091ms
memory: 7720kb
input:
bbbaabaababbaababbbbbbabbbbbbabaabbaaaaabbabbbbbabbabaabbbbaabaaababaaababbaaabababbabbababbbabaabbbabbabbabaabbbbaabaaabbaaabaaabbaaaaabaababbaabaaaabbbbababaababbabaaabababbaabbabbbabbababaaabbbbbabababbaabbbabaaabbaabaababaabbbaabbbaaabbbbabaabbbaaaabbbababaabbaaabaaababbbaabbbaabbbbbabababbababb...
output:
155673
result:
ok 1 number(s): "155673"
Test #20:
score: 0
Accepted
time: 949ms
memory: 7480kb
input:
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
121390
result:
ok 1 number(s): "121390"
Test #21:
score: 0
Accepted
time: 1015ms
memory: 7448kb
input:
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...
output:
196413
result:
ok 1 number(s): "196413"
Test #22:
score: 0
Accepted
time: 953ms
memory: 7460kb
input:
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
121392
result:
ok 1 number(s): "121392"
Test #23:
score: 0
Accepted
time: 1014ms
memory: 7492kb
input:
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...
output:
196416
result:
ok 1 number(s): "196416"
Test #24:
score: 0
Accepted
time: 963ms
memory: 7656kb
input:
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
121394
result:
ok 1 number(s): "121394"
Test #25:
score: 0
Accepted
time: 1015ms
memory: 7508kb
input:
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...
output:
196419
result:
ok 1 number(s): "196419"
Test #26:
score: 0
Accepted
time: 1276ms
memory: 7840kb
input:
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
196415
result:
ok 1 number(s): "196415"
Test #27:
score: 0
Accepted
time: 1423ms
memory: 7832kb
input:
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...
output:
317806
result:
ok 1 number(s): "317806"
Test #28:
score: 0
Accepted
time: 1284ms
memory: 7900kb
input:
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
196417
result:
ok 1 number(s): "196417"
Test #29:
score: 0
Accepted
time: 1401ms
memory: 7896kb
input:
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...
output:
317809
result:
ok 1 number(s): "317809"
Test #30:
score: 0
Accepted
time: 1299ms
memory: 7936kb
input:
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
196418
result:
ok 1 number(s): "196418"
Test #31:
score: -100
Wrong Answer
time: 1415ms
memory: 7824kb
input:
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...
output:
317812
result:
wrong answer 1st numbers differ - expected: '317811', found: '317812'