QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#130096#5037. 回文pandapythoner#10 465ms7444kbC++201.9kb2023-07-23 16:17:232024-07-04 00:54:26

Judging History

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

  • [2024-07-04 00:54:26]
  • 评测
  • 测评结果:10
  • 用时:465ms
  • 内存:7444kb
  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-23 16:17:23]
  • 提交

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%