QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#164145 | #4275. Escape Sequences | wsyear | WA | 10ms | 6452kb | C++17 | 1.9kb | 2023-09-04 20:19:16 | 2023-09-04 20:19:17 |
Judging History
answer
#include <bits/stdc++.h>
#ifdef dbg
#define D(...) fprintf(stderr, __VA_ARGS__)
#define DD(...) D(#__VA_ARGS__ " = "), debug_helper::debug(__VA_ARGS__), D("\n")
#include "C:\Users\wsyear\Desktop\OI\templates\debug.hpp"
#else
#define D(...) ((void)0)
#define DD(...) ((void)0)
#endif
#define rep(i, j, k) for (int i = (j); i <= (k); ++i)
#define per(i, j, k) for (int i = (j); i >= (k); --i)
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
using ll = long long;
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;
using namespace std;
const int N = 200010;
int n, m, a[N], b[N], fail[N], kmp[N];
char s[N], t[N];
bool check() {
// 判断 b 是否在 a 中出现
fail[1] = 0;
rep (i, 2, m) {
int j = fail[i - 1];
while (j && b[i] != b[j + 1]) j = fail[j];
fail[i] = j + (b[i] == b[j + 1]);
}
rep (i, 1, n) {
int j = kmp[i - 1];
while (j && a[i] != b[j + 1]) j = fail[j];
kmp[i] = j + (a[i] == b[j + 1]);
}
rep (i, 1, n) if (kmp[i] == m) return 1;
return 0;
}
int main() {
cin.tie(nullptr) -> ios::sync_with_stdio(false);
cin >> (s + 1) >> (t + 1);
n = strlen(s + 1), m = strlen(t + 1);
rep (i, 1, n) a[i] = s[i] - 'a';
rep (i, 1, m) b[i] = t[i] - 'a';
int ans = -1, cnt = 0;
bool f = 0;
while (n && m) {
if (check()) { ans = cnt; break; }
cnt++;
bool fa = 1, fb = 1;
rep (i, 1, m) {
if (i & 1) fa &= (b[i] == 0);
else fb &= (b[i] == 0);
}
if (m == 1) break;
if (fa) {
if ((m & 1) && !f) n--, f = 1;
int mm = 0;
rep (i, 1, m) if (!(i & 1)) b[++mm] = b[i];
m = mm;
} else if (fb) {
if (!(m & 1) && !f) n--, f = 1;
int mm = 0;
rep (i, 1, m) if (i & 1) b[++mm] = b[i];
m = mm;
} else {
break;
}
}
cout << ans << '\n';
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5672kb
input:
b ab
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 1ms
memory: 3688kb
input:
ababa bab
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: 0
Accepted
time: 1ms
memory: 5748kb
input:
a b
output:
-1
result:
ok 1 number(s): "-1"
Test #4:
score: 0
Accepted
time: 1ms
memory: 5736kb
input:
abbb baa
output:
2
result:
ok 1 number(s): "2"
Test #5:
score: 0
Accepted
time: 1ms
memory: 3628kb
input:
abaabb abaab
output:
0
result:
ok 1 number(s): "0"
Test #6:
score: 0
Accepted
time: 1ms
memory: 5796kb
input:
aaab aaba
output:
-1
result:
ok 1 number(s): "-1"
Test #7:
score: 0
Accepted
time: 1ms
memory: 5748kb
input:
bbbabbbbbbbabbabbbbaaaaaaaabbabaaabababaaababbbabaabbabbaababbabbbbbbbbbabbabbabbbbabaababaaaaa bbaabbaabbbaaaaabbaaaaaabbabbaababababbbbabaabbbabbaaaabababaabbbababbabbbbaabbbbbbb
output:
-1
result:
ok 1 number(s): "-1"
Test #8:
score: 0
Accepted
time: 1ms
memory: 3760kb
input:
abbbbbabbbbabbbbaabbbaabaaabab abababbabaaabbaaaaabbbabbaabbaaabaabababbb
output:
-1
result:
ok 1 number(s): "-1"
Test #9:
score: 0
Accepted
time: 1ms
memory: 5752kb
input:
bbaabaabaaab aaaaaaaaaaaaaaa
output:
2
result:
ok 1 number(s): "2"
Test #10:
score: 0
Accepted
time: 5ms
memory: 6028kb
input:
abaabaaabbaabbbbabbbbbbbbbabbababbabbbbbbabbbaaaaaaaabaabaaabbabbbabaababaaaabaaaaaaaaaabaabbbbbbaababbbabbaaaabbabaaaabababaabaaabbbbbbbbbbbbabbbaaaaaaaaaabbbababbabaaabbaaababbaaaaaabaaabaabbaababaaabababaaaabaabaaaabbabbbbaaabbbababbabbaaaaaabaaaababbbbbbaabababbbbbababababbbabbbbaabaaaabbaabaabb...
output:
13
result:
ok 1 number(s): "13"
Test #11:
score: 0
Accepted
time: 8ms
memory: 6200kb
input:
bbbabaabbaabbabababbbabbabaaabaaaaabbababbaababaaabbbabababbbaaaaaaaaabbbbbbbbbbababbbbaababbbabbbbaaababbaabaabaaaabababaabbabaaaabaaaabaabbaaaabaabbbbaaabaabababbbabbaababbaaababaaaaabaababbbaabbaabbbabaaabaababababaaabbbaaaabbbbaabbabaabababaabbbabbbabaaaabbabaababbbaaaaabaaabbaababbababaaaaabaab...
output:
13
result:
ok 1 number(s): "13"
Test #12:
score: 0
Accepted
time: 4ms
memory: 5992kb
input:
bbabaaaaabababbabbaabaaababaababaaaaabbbaabaabbbababbababababbaaabbbaaababbbbbbabbaabaaaabbbbabaabbbabaaaabbaaababbbaabbaaaaaabbbaaaaaaaabbabbaaaaabababbabbabbbaabaaaaaaabbbabbabbbbbabaabababbaaabbbbbbbbabaaaaabbbabbaaabaabbaabaabaaabbabbbbbabbbabaaaababbbabaabbaaaabbaaabbaabaaabbabababbbbbabbaabaaa...
output:
11
result:
ok 1 number(s): "11"
Test #13:
score: 0
Accepted
time: 2ms
memory: 5908kb
input:
aaaababaababbabbbbbbbaaaaabbbbabbbabaaaabbbababaaaaaaabbbbbbabababbbbabbababbbbabbaaababaabbbbabbaaaaaaabbabaababaaaaaaabbbbaaabaabbbaababbbaababbbbbaaabaabaabbaaabaababbbbabbabbababbbbababbbaabbbabaabaabaaabbaaabbbbbabbbabababbaaaaabbbbbbbbaabaabbbbbaaaaaaaabababaabaababaaaabaaabbbbaaaabbbbabbaaaab...
output:
12
result:
ok 1 number(s): "12"
Test #14:
score: 0
Accepted
time: 1ms
memory: 5832kb
input:
abbaabaabaabababababbaaaaababbbabaabbbbbaaaababbbbbbabababaaaabbababbabbabbaaaaabbbbabaababaababbbbbaaaabbabbbbabaaaaababbabbaabababbbabbababbbbbaabbabbaaabbbabbaababbbbbabbabaabbbabbbaaabbbababaabbaababbabaaaaabaabbbbbbbabbaabaaabbbbabbabbabbabbaabaababaaabbaababbaaaabaababaabaabbababbaaabbaabaaaba...
output:
3
result:
ok 1 number(s): "3"
Test #15:
score: 0
Accepted
time: 6ms
memory: 6008kb
input:
abbaabbbabaaaaaaaaabbbaababaabaaababbaaaabababbbaababbabababababbbaababaaaaabbbbbabaaabbbbaabaabbaabbbbbbbababbbababbbbaaaaaabbbaaaaababababbaaaaabaabbaaaabbaabaaaabbaaaaabaaaaaaabbbaabaaabababaabaababaabbaaabbbaababbbababbbaaabaaaaaaabbabbabbaaaabbaabbabbaaaaaabababbbbabaaaaabbaaabaaaaabbbbaabababa...
output:
10
result:
ok 1 number(s): "10"
Test #16:
score: 0
Accepted
time: 6ms
memory: 6008kb
input:
bbbababbabbbaabbbabbbabbbabaaaaaaaaabaabbabbaaaaabbbababbaabbaaaaababbbabaaaabbbabbbaabaaababababbaababbaabbaaababbbababbbbaabbabaabbabbaaabaaabbbbaaaabaaaabaababababbbabaabbbaabaabbbbababbbbbbbbabbababbbbaaaabaaabababaabaaaaabbbaaaaaabbabaabbabbaaaaaaabaaaaaaaabaabbabbabbabbaaabbabbbbaaabaabaabbbbb...
output:
12
result:
ok 1 number(s): "12"
Test #17:
score: 0
Accepted
time: 10ms
memory: 5092kb
input:
aaabbabbbbaaabaaaababbbabbaabbababbbbbbaaaaaabbababbbaabbaaaabababbabaaaabbbabaababbbbaaabababbaabbabbaaabbaababaababaababababbbbaababbbbbbaaababbbbaaabbbbbbbbaaabbbaaaababaabbaaabaaaabaaabbbaabaaababbaabbababbababbaaabbabbbababaaaabbaaababbabaaababaabaaaabbabbabaaababbbbaabaaaaabbbbbabbbbaabbbbbbbb...
output:
11
result:
ok 1 number(s): "11"
Test #18:
score: 0
Accepted
time: 7ms
memory: 6344kb
input:
bbbbababbaabbbbbbabbbaababbbabbaabbbbbbabbbababbbaabbbababbbbbbabbabbaababbaabbbbbbbabbbbbbabaabbabbabbbaabababbababaaababbbbbbbbbaaaaabbbaabbababbbabbababbbabbbbabbaabaaababaabaaababbbabbbbbabbbbbbbbabbbababbbbaababbbbabbbababbbbababbabbbaaabbaabaabababaaabbbbabbbbabbbbabbbbaaaaaabbabaabaabbaaaabab...
output:
8
result:
ok 1 number(s): "8"
Test #19:
score: 0
Accepted
time: 3ms
memory: 6300kb
input:
abbabbbbbbbababbaaabbabbbabbbababaabbbbbaabbababbbaabbbabbabbbbbababaabbabbbbabbaabbbababbbababbbbbaababbbbaaaababbababbabbabbabbaabbbbabbbbababaabbaabbbbabbbabbbbbbbaababbbbbbbbbbbbbbaababbbabbabbabaabbbababaabbbbababaababababbbbababbaaabbbbbababbbaaabbbbbabbaabbabaabaaaabbbaaaabbabbbbbabaabbaabbab...
output:
9
result:
ok 1 number(s): "9"
Test #20:
score: 0
Accepted
time: 9ms
memory: 6320kb
input:
aaababbbbbbabbbabbbbbbaaabbbbbbbaaaaaabbbbabbbbababaaaabaaabbaabbbbbbabbbaabbbaababaaababbabbbbbbabbababbbbbabbabbbbbbbbbbbbbaaaabbabbbbbbbbbbbbbabaaababbbbbbbbbbbbababbbabbbbaabbbbaabbabbbaababbbbbbaababbbbabbbbabbbbaaabbbabbbbababbbbabbabbabbbabbabbbabbbbaaaabbbbbabbaabbbbbbbabbbbabbbbbbbbabababab...
output:
11
result:
ok 1 number(s): "11"
Test #21:
score: 0
Accepted
time: 9ms
memory: 6136kb
input:
ababbbbaabbababbaaabababbabbabaabbbbaaaabaaabbbbbbbbbbbaaaabbaaabbbbababbbbbaabbbbabbabbbabbbbaababbbbbbbbaaaabbbabbbbaabbabbbbbbbbbbbababababbbbababbbbbbabbbbbbababababbababbababbaabbabbbbbbbbbbbbbabbbbbbbbabbbbbbbbbbabbabaaabbaabbaabbbbbbbbbbababaabaaababbbbbbbbbbbbbaabbbabbabbbabbbbbbbbbabbaaabba...
output:
12
result:
ok 1 number(s): "12"
Test #22:
score: 0
Accepted
time: 6ms
memory: 5384kb
input:
bbbbbabbbbababbbababbbbbbbbbbbabbbaabbabbbabbbabaaababbaabbbababbbbabbbbaabbbbbbabbabbbaabbbaabbbaaaabbbaabbbbabbbbbbbabaaababbbbbaabaaaabbababbbbbbababbbababbabbbbabbaaaababbbababbabaaababbbbbbabbabbaabbaabbbbbbabbabbabbbaaabaabbbbabbbbbabbbabbbabbbbbaababbbabbbbbabbbaabababbabbbaaabbbbbbbaabbbbbbb...
output:
13
result:
ok 1 number(s): "13"
Test #23:
score: 0
Accepted
time: 5ms
memory: 6272kb
input:
abbbbbbbbaaaabbaabaabbbaaabaabbbbbbabbbbbbabbbbbbababbbababbbbbbbbbabbbbabbaabbbbbbbbbbabbbabbbbabaaabbbbbabbbbbbbabbbbabaaaaabbbabbbabaabbbbbbbbbbbbaabbaabbbbaaabbbaababaabbbbabbbbabbbbabbbbabbbabaababaababbababbbbbbaaababababbbbbbbbabbbbaaabbbbbbbabbabbababbbbbabaabbbbbbbbabbbbbbbbaaabbabbbbbbbbba...
output:
9
result:
ok 1 number(s): "9"
Test #24:
score: 0
Accepted
time: 3ms
memory: 6452kb
input:
abbbaaaabbbabbabbbababbbabbbbaabbbbabbbbababbabaabbaababbbbbbbbabbbbbabbbbbbabbaabbbbbabaaabbbbaaabbabbbbbbbbbbbbbbbbbabbbbbbabbbbababaabbaaabbabbbbbbaabbabbbaabbbbbbbbabbbbbabbbabbabaaabbaabbbbabbbbaabbababbbbbabbabbbabbbaaaababbbbbabbbbbabbbbbbaabbaabbbaabbabbbbbababbbbbbbbababbabbbbbbaabbabbaabbb...
output:
9
result:
ok 1 number(s): "9"
Test #25:
score: 0
Accepted
time: 2ms
memory: 5028kb
input:
aaabbbbbbbbbbabbbbabbbaaababbbbabbbbbaaabbbbbabaabbbbbbbbbabbbbbbbababbbaabbabbabbbbbbbbaabaabbbabbabaaababbbabbbbbbbaabbabbbbaaaaababbaaababaaabbbbbbbababbbbbbbbbbbbabbbbbaaabbbbbabbbbbaaabbbbabbbabbbabbbbbbbbabaababbaaabababbbababbabbbbbabaababababbbaabbbbaababababbbaabbaabbaababbabaaababaabaabbba...
output:
5
result:
ok 1 number(s): "5"
Test #26:
score: 0
Accepted
time: 3ms
memory: 6256kb
input:
bbbbaaabbaaabbabbabbabbbbabbbbabbbbbbbabababababbbbabbabbbbbbbbbbbabbbbbabbaabbbbbbabbabbbbbbabaabbabbabbbbaabbabbbbbabbbbabaaabbbbbbabbbbaabbbbabbbbbbaababaaabbbabbbbbbbbabbaabbabbabbabbbbbbbaaabbbaaabbbbabbbbbbbbababbababababbabbbaaabbbbabbbbababbbbbababbbbbaababbbabaabaaabbbbbbabbbbbbbabaabbbbbab...
output:
8
result:
ok 1 number(s): "8"
Test #27:
score: 0
Accepted
time: 5ms
memory: 4832kb
input:
abbabbbbbbbaaaaababbbaababbbaaaababbbbaabbabbbabbbbbbabbaababbbabbabbbbbabaaabbbbababaaabbbaababbbabbbbbababaaababbababbabbbbbbabababbbaabbaabbabbabbaaaababbabbbaabbbbababbbaabbbaababbabbbbabbababbababbbabbbbbabaabbbabababaaaabbbbbbbaabbaabbbbbbababbbabbbbbbabbaabaaaabababbbabaababaababaababbbbababa...
output:
6
result:
ok 1 number(s): "6"
Test #28:
score: 0
Accepted
time: 10ms
memory: 5240kb
input:
bbaabababaaaaabababbbbbbbabbabbbbbbabaabbbbbabaabbbbbbbbbbababbbbbabbaabbabaabbbbbaababbaabaabbbbbbbaababaabbbababbbbabbbabbbbabbbbbbbbbababbbbbbaabaabbbbbabbabbbbaabbbaaabbaabbabbabaabbaababbbbbbabbabbbbbbbaabbabbbbbbabbabaababaabbabbbaabbaabbabbabbabaababbbbbbbbabbbbbbbaabaababaabbbbbbbbbababbabbb...
output:
13
result:
ok 1 number(s): "13"
Test #29:
score: 0
Accepted
time: 5ms
memory: 6392kb
input:
babbbbbbbbbabababbbbbbbbbabbabaababbabbabbbbaabbababbbbbababaababbbabbbaabbbaaabbbabababbababbbbabbbbabbaaabaabbbbbbabbbbbabbbbbbbbbbbbbbaababbbabbbbabbbabbabbbbabbabaaabbabababaabbabbababaabbaaaabbbaabaaabbbbbbbabbbababbbababaaabbbbbabbabbaabbaabbbbbabbababababbabbaaaaaabbbabbababbbbabbbabbbabbbbbb...
output:
5
result:
ok 1 number(s): "5"
Test #30:
score: 0
Accepted
time: 5ms
memory: 5396kb
input:
bbbbabbabababbbbbbabbbaaabbbbbbbbbbbaabbbbaabbbbbbbaaaaaaabbbbbbbbabaabbbabaabbbbbbababbabaababbabbbbababbbbabbaaababbbabaaaababaabbbbbbbaababbbbabbabaaabbbabbbaabbabaaaaabbbbbabbbabbababaaabbbbaababaabbaaaababbbbbbbbbaabbbababbbaabbbabbbbbbbbabbbbbaaabbbbbabbbbbbbbbbabbabbabbbbbabbabbabbabbbbbbabbb...
output:
8
result:
ok 1 number(s): "8"
Test #31:
score: 0
Accepted
time: 6ms
memory: 6388kb
input:
bbbbbbabbbbabbbbbbabbbbabbbbabaabbbbabbbaababbbababbabbbabbabbbbbbbbbbbbbbbbbbabbabbabbabbbbbbbbabaabbbbaabbabbabbbabbbbbbbbaaaabbabbbbbbbabababbbabbbabbababbbababbbaabbabbbababbaabbabbbaaabbbabbbbbbabaabbabaaaabbbabbbbbbababaabbbbbaaaabaabbaaabaabbaabbbbbaaaabbababbbbabbbabbbabbbababbabbaaaabbababa...
output:
6
result:
ok 1 number(s): "6"
Test #32:
score: 0
Accepted
time: 8ms
memory: 6208kb
input:
bbababbabbbbbbbbabbababbabaabbbaabbbabbbbbababbababaababaabbbbbabbabbabaabbbbbaababbabbbabbabbbbababbbbaabbabbabbbbababbbbababbbbbabbbbbabaabababbbbbbababaabaaaabbabbabbbbbbabbbabbbbbaabbbabbabbbbbbbbbbbbbbbabbbbbbbbbbbabbabbbbbbbabaaaabababbaabbbbbbaabbbaabbabbbbbabaabababbbabbaabbaaaaaabbbabbababb...
output:
9
result:
ok 1 number(s): "9"
Test #33:
score: 0
Accepted
time: 5ms
memory: 6328kb
input:
bbbbababbbbababaaaabbbbbbbbbbbbaaaababbbabbbbabbbbaabbaabbabbaababababbbbabbbabbbbbbbbaaabbbbabbbbbbbbaaaabbaabbababaabbbbbbbbbabbbabbbaababbababbababbbbabbaaaabbaabbbbaababaabbbbbbbbbaaabbabbbbbabbbbbbabbbabbbabbabbbaaabbbaababbabbbbabbabbbbabaabaabbbabbbbaabbbbaaaabaababbbbabbbbbaaabaabbbbbaabbabb...
output:
5
result:
ok 1 number(s): "5"
Test #34:
score: 0
Accepted
time: 8ms
memory: 6212kb
input:
aaaaabbbbabbbbbbbbbbbbaaababaaababbabaabbabbabaabaabbbabaababbbababbaaaabbabaaaababaabbbbabbbbaaabbabaabbbabbababbbaabbbbbbbbbabbabbbbabbabaabbaaabbbbbbbbaabaaabbbbbaabbabbabbabbbbbaabbbabbbbabbababbbbaabbabbbbbababbbabbbababbbbaabbaaabbbbbaabbabbbbbbabbabbbaababbbbbbaabbbabbbbabbbbbbababbaabbbabbbb...
output:
11
result:
ok 1 number(s): "11"
Test #35:
score: -100
Wrong Answer
time: 1ms
memory: 5992kb
input:
b aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
-1
result:
wrong answer 1st numbers differ - expected: '17', found: '-1'