QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #456156 | #7133. Substring query | propane | AC ✓ | 129ms | 24724kb | C++20 | 4.0kb | 2024-06-27 11:37:44 | 2024-06-27 11:37:44 |
Judging History
answer
#include<iostream>
#include<cstring>
#include<vector>
#include<array>
#include<algorithm>
using namespace std;
using LL = long long;
const int maxn = 4e5 + 5;
int tr[maxn * 32], ls[maxn * 32], rs[maxn * 32];
int root[maxn], idx;
int n, m;
void modify(int &u, int l, int r, int x){
if (!u) u = ++idx;
if (l == r){
tr[u] = 1;
return;
}
int mid = (l + r) / 2;
if (x <= mid) modify(ls[u], l, mid, x);
else modify(rs[u], mid + 1, r, x);
tr[u] = tr[ls[u]] + tr[rs[u]];
}
int merge(int x, int y, int l, int r){
if (x == 0 or y == 0) return x + y;
if (l == r){
tr[x] = (tr[x] + tr[y]) > 0;
return x;
}
int mid = (l + r) / 2;
ls[x] = merge(ls[x], ls[y], l, mid);
rs[x] = merge(rs[x], rs[y], mid + 1, r);
tr[x] = tr[ls[x]] + tr[rs[x]];
return x;
}
int query(int u, int l, int r, int L, int R){
if (u == 0) return 0;
if (l > R or r < L) return 0;
if (l >= L and r <= R) return tr[u];
int mid = (l + r) / 2;
return query(ls[u], l, mid, L, R) + query(rs[u], mid + 1, r, L, R);
}
vector<array<int, 3> > q[maxn];
int ans[maxn];
struct GeneralSuffixAutomaton{
struct Node{
int len, fa;
int ch[2];
}node[maxn];
int tot = 1, last = 1;
int c[maxn], id[maxn];
GeneralSuffixAutomaton(){
clear();
}
int new_node(){
++tot;
node[tot].len = node[tot].fa = 0;
memset(node[tot].ch, 0, sizeof node[tot].ch);
return tot;
}
void clear(){
tot = 0;
last = new_node();
}
void extend(int c){
if (node[last].ch[c]){
int p = last, q = node[p].ch[c];
if (node[q].len == node[p].len + 1) last = q;
else{
int nq = last = ++tot;
node[nq] = node[q], node[nq].len = node[p].len + 1;
node[q].fa = nq;
for(; p && node[p].ch[c] == q; p = node[p].fa) node[p].ch[c] = nq;
}
}
else{
int p = last, np = last = ++tot;
node[np].len = node[p].len + 1;
for(; p && !node[p].ch[c]; p = node[p].fa) node[p].ch[c] = np;
if (!p) node[np].fa = 1;
else{
int q = node[p].ch[c];
if (node[q].len == node[p].len + 1) node[np].fa = q;
else{
int nq = ++tot;
node[nq] = node[q], node[nq].len = node[p].len + 1;
node[np].fa = node[q].fa = nq;
for(; p && node[p].ch[c] == q; p = node[p].fa) node[p].ch[c] = nq;
}
}
}
}
void topsort(){
for(int i = 1; i <= tot; i++) c[i] = 0;
for(int i = 1; i <= tot; i++) c[node[i].len]++;
for(int i = 1; i <= tot; i++) c[i] += c[i - 1];
for(int i = tot; i >= 1; i--) id[c[node[i].len]--] = i;
for(int i = tot; i >= 2; i--){
for(auto [l, r, qid] : q[id[i]]){
ans[qid] = query(root[id[i]], 1, n, l, r);
}
root[node[id[i]].fa] = merge(root[node[id[i]].fa], root[id[i]], 1, n);
}
}
void insert(const string &s, int id){
last = 1;
for(auto c : s){
extend(c - 'a');
modify(root[last], 1, n, id);
}
}
}sam;
int main(){
#ifdef LOCAL
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
cin >> n >> m;
for(int i = 1; i <= n; i++){
string s;
cin >> s;
sam.insert(s, i);
}
for(int i = 1; i <= m; i++){
int l, r;
string s;
cin >> l >> r >> s;
int pos = 1;
for(auto c : s){
pos = sam.node[pos].ch[c - 'a'];
}
q[pos].push_back({l, r, i});
}
sam.topsort();
for(int i = 1; i <= m; i++){
cout << ans[i] << '\n';
}
}
这程序好像有点Bug，我给组数据试试？
詳細信息
Test #1:
score: 100
Accepted
time: 3ms
memory: 13960kb
input:
4 2 a b ab bab 1 3 a 1 4 ab
output:
2 2
result:
ok 2 number(s): "2 2"
Test #2:
score: 0
Accepted
time: 0ms
memory: 11632kb
input:
6 10 b ba a a b abab 4 4 b 1 2 b 1 2 b 2 4 b 5 6 a 2 6 a 5 5 a 3 4 b 2 2 b 1 3 a
output:
0 2 2 1 1 4 0 0 1 2
result:
ok 10 numbers
Test #3:
score: 0
Accepted
time: 0ms
memory: 11732kb
input:
5 3 bab b ab aba b 1 1 abba 1 2 abbab 1 2 b
output:
0 0 2
result:
ok 3 number(s): "0 0 2"
Test #4:
score: 0
Accepted
time: 2ms
memory: 11716kb
input:
6 10 b bbab b ba a a 2 6 b 4 6 b 2 5 b 3 5 b 1 6 b 3 5 b 2 3 b 2 4 b 3 4 b 5 6 b
output:
3 1 3 2 4 2 2 3 2 0
result:
ok 10 numbers
Test #5:
score: 0
Accepted
time: 2ms
memory: 11736kb
input:
10 10 b a b a b a a b b a 7 9 b 4 9 b 2 6 b 2 5 a 3 5 b 1 10 a 7 10 a 1 9 b 3 8 b 3 10 a
output:
2 3 2 2 2 5 2 5 3 4
result:
ok 10 numbers
Test #6:
score: 0
Accepted
time: 2ms
memory: 11948kb
input:
9 10 a b ba b a a b a b 5 9 b 5 8 a 1 8 a 3 4 a 1 2 b 9 9 a 6 9 b 3 3 a 2 4 a 5 9 a
output:
2 3 5 1 1 0 2 1 1 3
result:
ok 10 numbers
Test #7:
score: 0
Accepted
time: 0ms
memory: 11656kb
input:
10 9 a b b a b b b b b b 4 5 b 2 5 b 5 9 b 8 10 b 2 8 ba 6 9 a 7 10 b 1 8 b 2 4 b
output:
1 3 5 3 0 0 4 6 2
result:
ok 9 numbers
Test #8:
score: 0
Accepted
time: 2ms
memory: 11828kb
input:
7 7 b ba b a bba a b 4 5 b 3 5 a 2 3 a 4 5 b 2 7 ba 1 7 abb 1 6 a
output:
1 2 1 1 2 0 4
result:
ok 7 numbers
Test #9:
score: 0
Accepted
time: 2ms
memory: 11628kb
input:
9 8 b b a b b b b a ab 2 8 b 1 3 a 2 3 ba 7 9 ab 1 3 b 1 3 b 1 1 a 8 8 a
output:
5 1 0 1 2 2 0 1
result:
ok 8 numbers
Test #10:
score: 0
Accepted
time: 0ms
memory: 11920kb
input:
10 8 b a b b a a a b b b 4 8 b 3 6 b 1 5 ba 7 10 b 3 7 b 2 9 ab 3 6 b 4 5 b
output:
2 2 0 3 2 0 2 1
result:
ok 8 numbers
Test #11:
score: 0
Accepted
time: 2ms
memory: 11776kb
input:
6 10 b ba aba ab b a 4 5 b 2 5 a 1 3 a 2 3 b 3 3 b 4 6 b 1 2 b 1 4 b 1 4 b 6 6 b
output:
2 3 2 2 1 2 2 4 4 0
result:
ok 10 numbers
Test #12:
score: 0
Accepted
time: 0ms
memory: 13740kb
input:
758 618 b b b b b bba a a ba a a b b b b a b ba a a abb ba ab b abab ba bab b b bb b a bb ab b a b b b b b b b a a b b b bb bb b b a b b a b a a b b b a a a b b b b b b a b b ab a a bb ab b ba bb a a b a a a b a b b a aba b b b a a b b b a b bb b a b ab b b b ab ab b bb b a ba a b a a b b a a a b b ...
output:
326 93 156 322 271 2 105 68 126 1 0 20 231 31 12 396 113 0 301 21 177 356 69 113 0 7 12 11 0 266 167 284 45 414 0 257 10 121 1 20 52 116 265 392 153 317 20 122 173 312 0 126 110 41 6 0 16 32 14 135 128 163 0 488 72 55 25 154 487 358 13 100 11 100 47 42 285 45 154 42 212 196 0 3 38 49 35 379 64 0 251...
result:
ok 618 numbers
Test #13:
score: 0
Accepted
time: 0ms
memory: 13808kb
input:
816 799 b b ab b ba b a ab bb a a b a b b bbab a b ab bbab b b b a a b a a a b b b bb ba a b a b b b a a b a a b b b b ba b b a b b b b a a b b a b b a babb b bab b b bb b b ba a b b b ba a ba a a b b a a a a ab b a ba a a a ab b bba b a a a b a ab b b ab a ab a b b b a b b b a bb b a b b a b a b b ...
output:
69 266 53 217 434 3 415 6 124 448 4 181 187 250 221 219 115 222 257 144 26 118 105 172 2 102 12 182 44 399 198 337 117 26 53 356 137 15 28 140 41 360 103 88 7 58 1 30 5 34 154 193 69 347 110 279 28 324 90 236 216 71 38 195 42 74 291 6 79 14 23 222 5 102 110 168 4 149 282 332 18 145 19 388 162 160 68...
result:
ok 799 numbers
Test #14:
score: 0
Accepted
time: 0ms
memory: 11780kb
input:
476 831 a babb bb ba b a ba b bab b a a bba bab babbaba a b b abb b b a a abab ba bab b aba ba babbab a bab b a bba a b a bab a b bba ababbab a bab ab b a a a ba b a a ba b b ba b bb a b ab ab ba babbab a b ba b abbab b ab ba b ababba ba bb aba a b a ab b abba baba ab b a b b ba babb bab bb babbab b...
output:
61 95 283 106 206 93 118 6 122 91 38 61 193 46 164 12 15 230 35 276 176 237 190 21 123 30 149 307 27 222 168 27 95 58 126 41 217 136 107 129 37 40 332 93 169 102 154 84 86 5 123 45 62 206 77 215 15 55 36 121 21 60 352 29 101 235 28 143 199 82 212 32 54 13 213 68 213 31 55 224 22 292 85 271 19 93 0 1...
result:
ok 831 numbers
Test #15:
score: 0
Accepted
time: 0ms
memory: 11672kb
input:
625 938 a a b abba a bba b b aba ba b b bab b a a ab bab a b bb ba bb b a bba a b b ab b b b bab bab ab bb a b a b b b a ab aba a b bba b b abb ba a ba ba a a aba bbab a a ab b bab b b ab b b ab b b b a b ba ba b a a ba b bb a b aba abb b a a a b b bbab b abbab bb ba b aba a b a bb bb ab b ab ba b b...
output:
322 99 9 55 7 199 149 31 124 315 277 183 109 34 6 286 12 124 162 306 37 46 265 250 231 335 25 101 24 76 26 214 28 55 45 97 277 147 301 3 46 426 47 284 135 33 50 136 120 108 18 207 47 112 107 11 46 72 403 41 265 122 85 399 286 54 206 54 40 191 56 151 93 315 48 333 66 287 10 120 79 302 122 213 289 396...
result:
ok 938 numbers
Test #16:
score: 0
Accepted
time: 0ms
memory: 11996kb
input:
339 668 b b bb ba abbab bbabb a b bbabbaba abba b b abba bb b b bbabab bababbabb b abbaba b a bba bab bababb a babbababb ababba a b ababba a abba bba ab ababbab babbaba aba abbab aba ba bababb b bab b b bbab bb b bb b abbab aba b b ab b bbaba ab bab ab bbab babba ab bba abba bbab abba a bbababba bab...
output:
173 194 13 32 254 199 132 149 15 256 86 176 108 8 34 92 16 34 101 29 71 153 147 13 222 3 264 5 155 176 23 18 59 43 26 14 115 134 53 92 173 168 13 240 192 178 128 41 61 99 13 133 105 13 57 159 177 37 57 21 4 52 55 65 123 14 3 137 86 199 24 44 104 8 109 49 48 109 4 281 67 30 33 97 50 183 31 87 147 53 ...
result:
ok 668 numbers
Test #17:
score: 0
Accepted
time: 0ms
memory: 11984kb
input:
486 199 bbabb bb a bab a a bb bab b ba bab ba bab b a b b baba a ba a bb bbabab b a b bba ab bab bb ab b b ab a ab b a ba abb b babba ba b baba baba abb ba bba b b aba ababbab a ababbabb a b bb b b bba ab a b aba abab aba a ab bbab b ab ab b a b babab a b a b b ba bba bb b b b babbab b b bb abba b a...
output:
2 0 6 54 106 0 2 0 0 0 35 0 123 14 259 19 26 103 0 3 4 0 1 0 5 0 0 0 1 6 17 21 1 0 16 54 0 194 2 0 58 19 0 0 45 27 0 30 195 0 6 8 0 22 0 1 0 0 12 89 2 1 3 49 198 53 4 20 1 9 0 0 14 7 0 242 14 0 0 2 0 71 40 118 24 34 1 0 0 0 33 3 138 6 0 8 1 22 0 31 0 0 2 2 25 32 11 0 25 136 0 141 0 0 71 102 2 0 200 ...
result:
ok 199 numbers
Test #18:
score: 0
Accepted
time: 0ms
memory: 11688kb
input:
805 796 b a b b a b b a bb b b bb b b b ab b b a a a b b ba abba ba b b a b b a a a a ba b b b b bba b b a b a bba b a aba a bb ab b b bab a b b b b b b b b b b b b bb ab ab b a b b a a a b bab a b b a b ab ab bab b a b ab a a ba a ab b a b b ba a b bb abb b b b b bba b ba a ba b a ab bab b a ba bb ...
output:
271 11 154 36 6 23 43 33 26 118 343 489 88 163 399 11 163 21 20 197 222 0 194 22 15 209 83 262 39 27 14 382 80 8 154 4 221 315 160 6 54 24 67 77 517 201 227 256 116 334 117 175 261 199 186 7 15 191 64 65 47 41 0 326 293 201 166 20 25 22 334 195 36 169 30 358 101 236 62 11 53 203 27 443 3 55 37 153 5...
result:
ok 796 numbers
Test #19:
score: 0
Accepted
time: 2ms
memory: 11968kb
input:
862 717 b a b b bb a bab b b a b b b a ba a b a bab b b b b b ab a b a ab b a b a a b bb a b b b b b a a b b a ab a b a a a b ba b bb b a a b b a b a a a b b bb b a b b b a a a a b a ba bb b abb b b b ba bab a bb a b ab b b a b a b a a b bb a b b abb b b b b a b b b b b ab a b a b b a ab bb a b b a ...
output:
94 60 150 3 26 515 28 94 164 326 3 101 502 78 148 365 23 518 9 154 63 19 220 8 37 111 465 0 143 205 120 2 269 20 470 90 437 16 0 99 196 17 247 101 335 27 230 1 52 73 32 5 199 13 159 7 64 260 59 68 144 81 51 172 8 115 131 0 401 180 242 277 263 53 106 25 63 0 0 1 290 157 432 6 13 1 12 7 13 26 0 27 363...
result:
ok 717 numbers
Test #20:
score: 0
Accepted
time: 0ms
memory: 13860kb
input:
919 959 b a bba b b a b b bb a bb b a a b b b b a a a b b a a a b a b ba b b b b ab b a b a b b b b b a b b b a bb ba b b b a b a b ba b b ab b ab a ba b b b bb b a b a b a b b a b b a b b b b a b a a a a b b a b a ab b ab a b b a b a b a a b a b a b a b b b b a b b a b a a ab a a b a b a a b b b b ...
output:
364 86 67 126 187 92 397 326 37 2 98 116 373 191 201 232 460 77 231 16 327 86 185 171 317 515 164 189 330 180 21 26 48 2 239 229 296 113 339 349 284 224 257 187 337 51 224 104 95 72 264 307 34 69 268 108 109 8 93 272 35 117 213 329 206 69 102 257 42 99 138 188 40 174 63 25 193 215 60 54 239 106 20 2...
result:
ok 959 numbers
Test #21:
score: 0
Accepted
time: 3ms
memory: 11864kb
input:
982 970 b b a b b a b b a b b b b a b b a a b a a b b a a b a a b b b b a b b b b a b b a b b a a b b b a a b b a a b b ab a b a b a b a a a b b b b a a b a a a bb a a b a b b b b a a b b b b b a a a a b b a b a a b b a b b a a a a a b b b a a b a b a a b b b b b a b b b b b b a b a b a b b b b a b ...
output:
132 220 51 88 165 329 31 335 73 1 77 170 96 249 1 64 188 194 407 77 348 299 134 16 117 45 21 240 184 0 142 152 12 248 38 28 0 315 140 549 178 144 72 232 25 94 368 177 164 287 241 239 117 263 33 370 366 238 15 232 127 138 215 56 254 300 494 122 115 311 244 99 119 179 179 42 32 394 70 155 212 82 369 2...
result:
ok 970 numbers
Test #22:
score: 0
Accepted
time: 98ms
memory: 21168kb
input:
155674 133029 b ab a a b b a b ba b a ab aba bb a a b a ba b a ab a b a ba a abab b ab a b b a b b a ba b ab a b b b b ab a b bb b a b ba b bb b b a ba b abba b b b b b a b b bb b b b b ba b a ab b b a b b a b b a ab a b a a ba b b b ab b a babab b ab ba b a a a a ba ba b bb ab ab a b b ba b bb ab b...
output:
11782 44202 35799 11723 27 2161 44485 934 47827 69587 18959 89516 2008 18671 16199 7127 38553 65261 49902 89086 60969 78484 215 51099 2708 3884 47761 77420 5018 0 23279 6794 1877 150 13078 73 21 26779 16433 5960 1214 15963 11948 241 1156 67851 15 5151 10666 9956 38833 15361 61787 72553 42604 19500 5...
result:
ok 133029 numbers
Test #23:
score: 0
Accepted
time: 107ms
memory: 22740kb
input:
151840 164136 b b b a b a b a b ab a b a ab a b ba a b b b b b a b b b b b b abab b bbab b b ba b b ab bab a b a ba b b a b bb b b a b a b a a a b b a ab ab b abb a b b a a ab a b b a b ba ba b b bba b b b b b a ba a b ba a ab b b b b b bb b a ab bb a a a ab b ab aba b b a ba b b b b b a a b b bab b...
output:
31762 61791 25763 427 27275 1293 25670 17763 737 62604 84266 50318 39427 5334 6063 22955 13111 53930 20554 14375 55 12813 52042 27040 79369 10443 19845 25962 1287 6866 3569 62054 36615 2193 935 6194 43949 303 58201 22143 16488 7293 865 9053 44742 37271 437 26323 57584 1027 67261 9640 78609 16960 411...
result:
ok 164136 numbers
Test #24:
score: 0
Accepted
time: 124ms
memory: 20904kb
input:
196196 195243 b a a a b b b a b a b b a b a b a a a b b a a b b a b b b b b b b a a a b b b a b b b b a a a b b b a a b b b a b a b b b b a b a b a a b a a b b a b b b b b b a b b b a a b b b b a b b b b b b b b a b b b a b a a a a a b a b b b b a b a b b b a b a b b b b a b b b a b a a b b a a a a ...
output:
17919 19555 21789 619 72661 107084 110283 36411 51290 74973 8408 33669 67624 21963 14154 20774 28834 40003 31990 5283 12215 35108 18073 107153 104830 32049 12699 789 95724 93228 59338 24460 12340 17705 12797 13245 821 44376 21179 19063 35949 45855 49082 71523 600 2810 23841 46696 10971 11977 1979 11...
result:
ok 195243 numbers
Test #25:
score: 0
Accepted
time: 129ms
memory: 22888kb
input:
168307 185954 ab a b a b b b a a ab b b b a a bb a b bb a b b b b b a b ab b b ab bb b b a a a b a b b b a b a a b bba a b a a a b a b b b b b a ab a a a b a b b b b b b a b b b b b b b bb a b b b a b a b bba b bab a bb ba a a b b b b b b b b b b b b a b b b a b bba b b b b b bab a b b b b b b a a b...
output:
60624 52175 18519 33287 108464 32739 10039 7840 1493 39590 2667 78773 54970 31048 42626 4181 80818 25525 7501 1002 24212 14292 12760 26290 45380 4699 54886 86578 21456 75304 45372 18362 44974 44240 21149 23576 628 13365 45439 4822 9729 2988 15209 72169 46862 5189 6074 29725 196 8874 22615 19739 1284...
result:
ok 185954 numbers
Test #26:
score: 0
Accepted
time: 98ms
memory: 22584kb
input:
175589 153908 ab a b b b b b a ba b b b a b a a b ba a a a b b a ba ab b b b b b b b b bb b a b a a a b b ba b b a a b b ab bab b b ba a ba a a b b b bba a a a b b b a b b b b a a b ba b a ba a a a b b a a b a b a b a ab a b b a a ba a b b a bb b b a b b a ab b ab b a bb a ab aba bb b b b a b a b b ...
output:
3415 37315 79040 42473 10321 3214 5773 44493 27112 130 3522 84325 9830 28455 7284 5 17390 918 31106 13814 35158 3403 4623 331 14969 4917 71100 52403 28823 68255 1968 9790 30183 30662 33408 34968 21038 25008 25501 86647 31307 1156 3624 97384 3029 61664 41389 93167 19672 9919 24981 51719 81486 77665 3...
result:
ok 153908 numbers
Test #27:
score: 0
Accepted
time: 123ms
memory: 24724kb
input:
68421 198417 b a aba ab a baba b b ba babb babb ab bb abba ba b babab bb abbaba bbab babbabab ab bba abba bb b abb a a bb bb abbab babb ab bb b a abbab bab babb a abbababbabab ab ab babb a bababbab a a b bbababba ba b a abbabab bbabba abbaba babba ba bba a bbab ababba babb a ab b aba bab bab ababb a...
output:
46194 41146 16029 9350 29452 31835 16080 1253 80 868 22767 20653 15023 19770 13490 9931 15402 2721 1678 12261 51340 41502 52105 19941 10470 920 23048 13867 29290 34586 29021 2996 8516 53993 3476 8102 32201 12370 1216 26081 22103 12978 22792 23394 7950 22104 21476 3915 9066 2842 18118 43474 8996 1866...
result:
ok 198417 numbers
Test #28:
score: 0
Accepted
time: 110ms
memory: 22416kb
input:
185547 159277 b a b b a a b b b b b b a b b a a b a ab b b b b b b ab b ab b a a b a a a a b a b b b a b b b bb b ba a b b ab a b a a b b b ab b a a b b b b b b b b b a a b b a a a ab b a bb b a b a a a b a b a a b b b a b a a a b b b b b b a a a b b b b a b b b b a b b b b bb b b b b b b b ba b a b...
output:
33552 13709 958 555 2494 28695 14554 39608 47313 44148 21 8537 16548 1734 18668 36874 724 1056 19044 3227 58580 91 44558 4140 31806 29331 2878 107565 2629 2962 20102 180 26742 8285 151 248 32104 122 33305 61737 5680 11503 27622 56899 50372 26858 4280 18142 184 60441 48514 94014 23617 46 53008 40741 ...
result:
ok 159277 numbers
Test #29:
score: 0
Accepted
time: 104ms
memory: 23948kb
input:
84887 150776 b bbab ab abbaba a b b ba a b b abb b b a bb abba b a abab bab b bbabab b b ba b bbab ab a bbab a b b aba bb bab abb bb babab b ab ab b ab bab b abb ba ababb bb a b babba aba b b b a ab ba a b abb babab b a bbab b bab abba ab ab b bb babbab ab ababb abbaba a abba b bba a b abbab b b ab ...
output:
16098 1259 55258 46929 12902 4896 9689 4574 12613 45024 7295 6666 2417 25532 20916 25160 22128 27542 2918 10708 960 34734 37668 46296 22626 36831 23895 11498 29018 2308 28387 23210 47008 7773 6694 30976 4600 42378 32712 52948 12258 979 5119 39124 1625 16872 37110 6327 18805 4632 13610 11231 2966 202...
result:
ok 150776 numbers
Test #30:
score: 0
Accepted
time: 123ms
memory: 22212kb
input:
195504 181883 b b b a b b b ba a b a b a b a a b bb a a a b a b b a a a a b b a b b a b a a a b a a b b b a b b b a b a b a a b b a b b b b a ba b b a b b b b a a a b b b b a b b b a b b b a b b b b b a b b b b a b b a a a b a a b a a a b a b a b b b a a b b b b b b b b b a b a a b b a a b b b b a a...
output:
7318 31670 85063 104805 18261 28323 34753 15487 84875 163 22169 81246 5676 42566 7 34370 3174 24907 57783 11714 27386 29877 8801 73393 2336 881 56198 19260 21594 48922 7927 15234 14967 30994 20346 10029 8285 225 101256 24703 10052 11928 17460 9385 59569 19894 22020 49435 18851 17013 40104 11995 6026...
result:
ok 181883 numbers
Test #31:
score: 0
Accepted
time: 98ms
memory: 21124kb
input:
141730 129142 b b ab b b b b bbab ba b a b a a b b ab a ab b b b ba ba a b b b b a a ba b a b a b a a b ba ba b a ba ba bba a a b b ab a b b ba ab bb b ab a b a a b a a b ba a ab a b a a a b a b b abb ab aba ab a b a b b b a ab b b bba ba b abb a a b a bbab b b b a ba b b bb b b a bbab b ab ab b b b...
output:
2374 3956 1592 44483 58911 35468 20353 47179 88507 65185 15133 91435 223 17847 21825 1888 12491 1859 24193 39948 40668 12639 12361 2962 15049 921 1277 36788 24097 2578 16202 11080 152 3295 29529 8372 939 1281 55331 25419 3780 641 1184 56406 11868 1029 18774 6071 11097 2729 470 15098 26683 3405 15168...
result:
ok 129142 numbers