QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#130096 | #5037. 回文 | pandapythoner# | 10 | 465ms | 7444kb | C++20 | 1.9kb | 2023-07-23 16:17:23 | 2024-07-04 00:54:26 |
Judging History
answer
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#else
#endif
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define flt double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
const int alph = 27;
int n;
vector<int> a;
vector<int> b;
vector<int> prfx;
int q;
void prefix_function(int s) {
prfx[0] = -1;
for (int i = 1; i < s; i += 1) {
int j = prfx[i - 1];
while (j >= 0 && b[j + 1] != b[i]) {
j = prfx[j];
}
if (b[j + 1] == b[i]) {
j += 1;
}
prfx[i] = j;
}
}
int32_t main() {
if (1) {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
string s;
cin >> s;
n = (int)s.size();
a.resize(n);
for (int i = 0; i < n; i += 1) {
a[i] = s[i] - 'a';
}
b.resize(n + n);
prfx.resize(n + n);
cin >> q;
int lst_ans = 0;
for (int itr = 0; itr < q; itr += 1) {
int t;
cin >> t;
if (t == 2) {
int l, r;
cin >> l >> r;
l ^= lst_ans;
r ^= lst_ans;
--l;
--r;
int s = r - l + 1;
for (int i = 0; i < s; i += 1) {
b[i] = a[r - i];
}
for (int i = 0; i < s; i += 1) {
b[s + i] = a[l + i];
}
prefix_function(s + s);
int f = s + s - 1;
int cnt = 0;
while (f != -1) {
if (f < s) {
cnt += 1;
}
f = prfx[f];
}
cout << cnt << "\n";
lst_ans = cnt;
} else {
int i;
char c;
cin >> i >> c;
i ^= lst_ans;
int x = c - 'a';
--i;
a[i] = x;
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 52ms
memory: 3700kb
input:
aabbbabbbaaaaaaabbabbbaaaabaaaabbaabbaabbaaababbbabbbbabbbbaaaabbbabbbbbaaabbbabbaaaaabbbbbaaababbabbaaaaabaabbbbaaababaaabbaabbabbbabbbbaaaaabbbbbbbabbbaabbbabbabbbababbabbbbaaaaabbaababbbbaabbaaaaaabaaabbbaaababbbbaabaaaaababababbbbbbaaaabbbbaaababaaabbaabbbbbaaaabbaaaabaaaaaababbababaaaabaaababaa...
output:
2 3 5 3 3 3 2 3 4 2 4 2 4 2 3 3 3 2 2 2 2 2 2 3 4 2 2 3 2 2 4 3 3 2 3 3 4 3 3 4 4 2 3 4 2 2 4 2 4 3 2 2 2 3 3 3 4 4 3 3 2 3 3 2 3 3 4 2 2 4 2 3 2 3 3 2 3 2 2 3 2 2 3 6 2 2 3 7 4 3 2 2 2 2 3 4 4 4 4 2 2 3 2 4 2 2 2 3 3 2 2 2 2 3 3 4 3 2 3 3 2 2 4 5 4 2 2 5 3 3 3 3 2 4 2 3 2 3 3 3 2 4 4 5 2 2 3 5 3 3 ...
result:
ok 2509 tokens
Test #2:
score: 0
Accepted
time: 26ms
memory: 3920kb
input:
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
188 1078 673 914 360 4255 2205 3628 77 3608 230 494 128 848 801 1335 4079 3059 636 2882 3524 45 1174 506 3570 4172 1289 595 3829 1532 179 1274 2574 1098 2817 226 2580 887 989 1829 3656 181 2056 3315 786 117 2519 2742 3787 1080 3138 686 1605 239 1533 2658 2096 753 3400 219 1815 117 1645 52 1671 121 2...
result:
ok 2519 tokens
Test #3:
score: 0
Accepted
time: 26ms
memory: 3656kb
input:
bbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbbbbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbbbbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbbbbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbbabbba...
output:
12 8 12 24 30 18 11 8 32 18 10 32 26 11 11 15 18 6 18 19 13 21 10 13 20 16 10 10 10 9 16 11 32 14 24 20 29 15 10 17 10 8 8 22 31 9 9 18 25 10 14 16 22 24 15 15 11 13 33 7 13 21 7 19 12 12 17 7 23 15 2 10 16 15 9 14 6 18 10 8 18 20 21 5 11 18 3 17 13 17 8 11 17 7 6 7 11 10 9 20 9 28 19 10 14 11 24 8 ...
result:
ok 5000 tokens
Test #4:
score: 0
Accepted
time: 19ms
memory: 3716kb
input:
mkmamkmlmkmamkmnmkmamkmlmkmamkmamkmamkmlmkmamkmnmkmamkmlmkmamkmumkmamkmlmkmamkmnmkmamkmlmkmamkmamkmamkmlmkmamkmnmkmamkmlmkmamkmkmkmamkmlmkmamkmnmkmamkmlmkmamkmamkmamkmlmkmamkmnmkmamkmlmkmamkmumkmamkmlmkmamkmnmkmamkmlmkmamkmamkmamkmlmkmamkmnmkmamkmlmkmamkmpmkmamkmlmkmamkmnmkmamkmlmkmamkmamkmamkmlmkma...
output:
5 8 5 6 5 6 7 7 5 8 5 5 6 5 9 6 5 6 7 8 5 5 8 6 4 5 8 5 8 4 6 4 5 6 5 1 5 7 4 5 7 3 5 8 9 6 4 5 5 4 7 7 5 7 8 7 6 5 7 1 5 5 6 6 6 6 7 6 6 4 5 5 6 3 8 7 5 6 6 7 4 4 7 7 6 6 7 8 6 7 7 4 7 6 8 3 5 7 3 6 7 6 4 7 6 4 5 6 6 4 6 7 4 5 5 5 4 4 5 6 3 4 4 5 4 7 5 4 9 6 5 5 3 4 5 8 4 5 5 6 4 6 6 6 4 9 7 4 6 6 ...
result:
ok 5000 tokens
Test #5:
score: 0
Accepted
time: 29ms
memory: 3716kb
input:
babababababababababababababababababababababababababababababababbbabababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababbbabababababababababababababababababababababababababababababababbbabababababababababababababababababababababa...
output:
58 13 6 23 52 35 39 46 17 43 37 33 31 8 51 12 9 52 57 14 28 17 31 21 59 50 55 50 18 10 54 7 44 11 10 3 12 19 9 8 5 7 22 4 38 15 10 14 26 11 21 18 33 12 3 8 23 34 41 18 7 18 26 7 12 29 34 6 4 15 16 20 15 8 50 23 7 51 18 4 11 7 20 14 33 19 12 9 10 6 8 21 28 22 21 18 12 18 4 15 17 13 8 16 7 14 10 4 5 3...
result:
ok 2443 tokens
Test #6:
score: 0
Accepted
time: 36ms
memory: 3932kb
input:
aaaaaaaabaabaaaaaaaaaaaaaaaabaabaaaaaaaaaaaaaaaabaabaaaaaaaaaaaaaaaabaabaaaaaaaaaaaaaaaabaabaaaaaaaaaaaaaaaabaabaaaaaaaaaaaaaaaabaabaaaaaaaaaaaaaaaabaabaaaaaaaaaaaaaaaabaabaaaaaaaaaaaaaaaabaabaaaaaaaaaaaaaaaabaabaaaaaaaaaaaaaaaabaabaaaaaaaaaaaaaaaabaabaaaaaaaaaaaaaaaabaabaaaaaaaaaaaaaaaabaabaaaaaaaa...
output:
43 25 18 13 12 27 16 18 22 24 13 20 34 18 5 27 26 27 8 10 6 9 9 14 22 15 34 25 19 24 19 18 13 7 21 14 2 33 7 46 16 18 19 12 25 8 7 14 22 2 2 12 19 3 20 15 18 10 8 8 8 12 5 12 18 22 7 15 16 36 21 11 11 14 8 13 12 2 5 40 14 15 2 5 11 4 12 16 11 9 9 6 6 18 16 11 15 18 13 15 8 24 19 9 5 15 18 8 13 5 31 ...
result:
ok 2498 tokens
Test #7:
score: 0
Accepted
time: 27ms
memory: 3716kb
input:
baabbaabbaabbaabbaabbaabbaabbaabbaabbaabbaabbaabbaabbaabbaabbaabbaabbaabbaabbaabbaabbaabbaabbaabbaabbaabbaabbaabbaabbaabbaabbaabbaabbaabbaabbaabbaabbaabbaabbaabbaabbaabbaabbaabbaabbaabbaabbaabcaaaaaaaacbaabbaabbaabbaabbaabbaabbaabbaabbaabbaabbaabbaabbaabbaabbaabbaabbaabbaabbaabbaabbaabbaabbaabbaabba...
output:
67 7 4 13 81 3 8 92 28 86 94 92 71 23 73 26 24 13 71 88 98 42 70 45 82 63 5 80 57 49 48 77 88 5 98 96 65 52 11 24 52 51 76 90 9 10 58 43 36 48 82 73 10 14 90 54 74 12 32 36 71 46 8 46 20 38 22 68 54 73 66 32 95 63 52 7 40 97 27 13 42 59 41 14 9 44 53 52 92 30 36 27 86 90 59 95 12 36 42 16 24 58 23 5...
result:
ok 5000 tokens
Test #8:
score: 0
Accepted
time: 24ms
memory: 3700kb
input:
caaccaaccaaccabccbaccaaccaaccaaccaaccaaccaaccabccbaccaaccaaccaaccaaccaaccaaccabccbaccaaccaaccaaccaaccaaccaaccabccbaccaaccaaccaaccaaccaaccaaccabccbaccaaccaaccaaccaaccaaccaaccabccbaccaaccaaccaaccaaccaaccaaccabccbaccaaccaaccaaccaaccaaccaaccabccbaccaaccaaccaaccaaccaaccaaccabccbaccaaccaaccaaccaaccaaccaac...
output:
10 10 11 11 11 10 10 10 8 10 11 11 9 9 10 10 10 11 10 11 9 10 10 11 11 11 10 11 11 11 11 11 11 11 11 10 10 10 10 11 11 11 10 11 10 10 10 11 10 10 10 10 10 11 11 11 11 10 11 11 11 10 11 11 11 10 10 7 11 11 10 11 10 10 11 10 11 10 10 7 11 11 10 10 11 11 10 10 2 11 11 11 5 11 11 11 11 11 10 10 10 11 11...
result:
ok 1667 tokens
Test #9:
score: 0
Accepted
time: 25ms
memory: 3636kb
input:
cabccabbbbbbaccbaccabccabbbbbbaccbaccabccabbbbbbaccbaccabccabbbbbbaccbaccabccabbbbbbaccbaccabccabbbbbbaccbaccabccabbbbbbaccbaccabccabbbbbbaccbaccabccabbbbbbaccbaccabccabbbbbbaccbaccabccabbbbbbaccbaccabccabbbbbbaccbaccabccabbbbbbaccbaccabccabbbbbbaccbaccabccabbbbbbaccbaccabccabbbbbbaccbaccabccabbbbbb...
output:
38 38 38 37 38 38 38 9 37 38 8 38 37 38 38 38 38 38 38 37 27 38 38 38 38 38 38 30 38 38 38 38 38 38 38 38 24 38 38 38 38 38 38 38 38 38 37 38 5 38 32 25 38 38 38 38 38 38 38 38 38 38 38 37 38 37 38 31 38 38 38 38 38 38 12 38 38 37 38 38 38 38 37 38 38 38 23 38 38 38 38 24 38 38 38 38 38 35 38 38 38 ...
result:
ok 1667 tokens
Test #10:
score: 0
Accepted
time: 1ms
memory: 3696kb
input:
baaabbbaaabbbbaaababbababbabbbbaaaababaababbbbababababbbaabbbaababaaaababbbaaabaaababbababaaabbabbbaaabbabbbabaabaaaababbbbabbbbbaabbabbaaaabaaabababbbaababbbaaaaaababbabaaabaaaabbbabbbaababbbbbbbbaabbbaabbabaabababbaabaabaabbbbbaaababbbbabbbababababaabbababaabbabbbbbbaaaaaaabaabbabbabaabbbbbaaaaaba...
output:
3 3 2 3
result:
ok 4 tokens
Test #11:
score: 0
Accepted
time: 97ms
memory: 3720kb
input:
abbaaabaabbbaabbabbbbbbaabbbbabbaabababaabbabbabaaabbabbbaaaabbabbaabbbabbbabbababaaaabbabbaabababbbaaababaababbabbaaabbbaabaaaaaabbbabbababaabbbbbabbbaaaaaaabbaaaabaaababbababaabaaabbbaaabbaabbabbabbbababbabbbbbbbbaabbabbbabbbbbbbababaabbbaabaabaabaaabababbaabbbbaaabbbbabbaabbbabbbababaababbabbabba...
output:
3 4 2 2 4 2 2 4 3 5 2 2 3 4 3 2 3 4 6 2 2 2 2 2 5 3 4 3 3 2 2 2 2 5 2 3 2 3 2 3 2 3 2 4 2 2 3 2 2 3 5 2 2 7 3 2 3 2 3 3 2 2 3 4 3 2 4 2 2 2 3 3 3 3 3 2 3 3 3 5 2 4 2 3 3 3 3 3 3 2 4 4 3 4 2 2 3 3 6 2 5 4 2 2 4 2 5 3 3 2 5 4 3 3 3 3 4 3 2 3 2 4 2 3 6 3 3 2 3 3 2 3 3 5 2 3 4 3 5 3 3 3 3 4 2 3 3 2 3 2 ...
result:
ok 4997 tokens
Test #12:
score: 0
Accepted
time: 13ms
memory: 3700kb
input:
lxxhwqorbxrdzedxlvymggyicczuafgyovixrzmptqfmjyjfpamcsehmfazbvfwdgeftgbtyurnnykwjhzfqqsyiyzkpwlmspjsxdkjtpgzbrvwwcjqejmuillhgtbhwtwmvhacfphrcgwoaihjzkuccmwuidivmpjcezbjywhbqtdgrhlrskcwmecflzpjbuutlocivcfvbcdvlnfchtvvcpoubnjwfwvzvpyvhkvxdmleyvucrondntpaonjybzarkgjnkuuvipkqgvwzzzopwyfnmodnmdziueescfttr...
output:
1 1 1 1 1 2 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 2 2 1 2 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
result:
ok 2493 tokens
Test #13:
score: 0
Accepted
time: 27ms
memory: 3704kb
input:
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
849 1135 1444 1346 1445 536 3077 2631 1447 672 2214 2149 2090 4054 846 559 22 92 4224 161 2280 572 2347 2599 778 4093 750 3647 2142 642 474 1395 776 645 46 4141 2272 771 1564 207 4284 2896 3097 2829 306 1383 394 1776 1284 3933 102 510 1101 3639 1336 1292 2803 1159 601 1464 2585 673 281 1340 272 3310...
result:
ok 2478 tokens
Test #14:
score: 0
Accepted
time: 145ms
memory: 3684kb
input:
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 ...
result:
ok 4999 tokens
Subtask #2:
score: 0
Time Limit Exceeded
Test #15:
score: 0
Time Limit Exceeded
input:
aabababbabbbbbbabbababaaaabababbabbbbbbabbababaaaabababbabbbbbbabbababaaaabababbabbbbbbabbababaabbbaaabbaabbbbaabbaaabbbaabababbabbbbbbabbababaaaabababbabbbbbbabbababaaaabababbabbbbbbabbababaaaabababbabbbbbbabbababaabbaaabaaaaaabaaabbaabababbabbbbbbabbababaaaabababbabbbbbbabbababaaaabababbabbbbbbabb...
output:
41 43 154 118 55 165 48 163 119 207 147 145 33 67 114 124 154 9 104 307 102 73 39 364 79 177 53 39 88 264 77 114 79 195 150 153 157 46 129 136 147 25 309 11 12 258 259 133 355 50 116 336 13 127 18 34 122 161 38 99 290 92 355 166 59 152 41 182 103 282 166 23 86 173 32 122 60 127 287 20 83 214 119 144...
result:
Subtask #3:
score: 0
Time Limit Exceeded
Test #21:
score: 10
Accepted
time: 465ms
memory: 7444kb
input:
abbaaaabbabaaaaaabaabbaabbababbaaabbabbbabaabaabaaaaabaabbbbabbabbabbbababbbababababbbbabaabbaaababbbbbababbbbaabbbaaabaababababaabbbbbbaababaabbaaabaabbaaababbabbabbbbaaaaabaaabbbabbbbbbabbbabbabaabbbbbbbaaaabbaaaababbbaaaaaaababaabbbbaaabaaabbaabbbbbbababbaabbaaabbabbbbbabaababbaabaaaabbbbabababba...
output:
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 8 8 8 8 ...
result:
ok 198 tokens
Test #22:
score: -10
Time Limit Exceeded
input:
abbaababbabababbbbabababbbaaaabababbbbaabaabbbbabbbabbaabababbbabaaabbabbaabbbbbbaaababaababbbaabbbbaabbbaaaaaabaabbaabbaaaabaaabbaabbbaabbbababbbabbaaababaabaaabaabbabababaaaabaabbbbaaabbbbbbabbbbababbaabaabbbbabbaaabbaabaabbaabaabaaaaaabbaaabbbbbabbbbbaaabbabbabbaababaaabbabbaaaaaabbababbbaabbaabb...
output:
result:
Subtask #4:
score: 0
Time Limit Exceeded
Test #27:
score: 0
Time Limit Exceeded
input:
babbaaabbbbbbbabbbababaabbbbbababababbaabaabbbbbbabbbbbbbbbbababbbbabbaabbbaabaabbabbbaabbabbbabbababaababbbabbbbaabbabbabbaaaabbbaaabbbbaabbaaaaaaabbbabbbaaabaababaaabaaaabaaaababaaaaababaaaabaabbaaaabbbabbaabaabbbabbbbbaaabaababbbaaaaabbbbaaabbbbaabbabbbbabbbabbaaaaabaabaaaabbbabbbbbaabbbbabbbbaab...
output:
result:
Subtask #5:
score: 0
Time Limit Exceeded
Dependency #1:
100%
Accepted
Test #35:
score: 0
Time Limit Exceeded
input:
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
199105 199317 198628 198977 198643 198338 198952 198567 198980 198350 199045 199831 199124 199126 199123 199367 198992 198131 198623 199391 199376 199431 198418 198674 199222 199031 198833 198400 199208 198925 198477 198700 198952 199129 199580 199549 198972 199285 199185 198739 199281 199208 198920...
result:
Subtask #6:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%