QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#181332 | #5256. Insertions | ucup-team1209# | AC ✓ | 16ms | 9124kb | C++20 | 9.2kb | 2023-09-16 17:47:57 | 2023-09-16 17:47:58 |
Judging History
answer
#include <bits/stdc++.h>
#define cs const
#define pb push_back
using namespace std;
using pi = pair <int, int> ;
using ll = long long;
cs int N = 1e5 + 5;
char S[N], T[N], P[N];
int n, m, k;
void work_skip(char *T, char *P, vector <bool> & mat) {
// mat[i] P[i, k] ~ T
string S = " " + string(T + 1) + string(P + 1);
int l = S.length() - 1;
vector <int> lcp(l + 1);
int mx = 1, pt = 1;
lcp[1] = l;
for(int i = 2; i <= l; i++) {
if(i <= mx) lcp[i] = min(lcp[i - pt + 1], mx - i + 1);
while(i + lcp[i] <= l && S[i + lcp[i]] == S[1 + lcp[i]]) ++ lcp[i];
if(i + lcp[i] - 1 > mx) pt = i, mx = i + lcp[i] - 1;
}
for(int i = 1; i <= k; i++) {
if(lcp[i + m] >= m) mat[i] = 1;
}
}
void work_mat(char *T, char *P, vector <bool> & mat) {
// mat[i] P[i, k] ~ T
string S = " " + string(T + 1) + string(P + 1);
int l = S.length() - 1;
vector <int> lcp(l + 1);
int mx = 1, pt = 1;
lcp[1] = l;
for(int i = 2; i <= l; i++) {
if(i <= mx) lcp[i] = min(lcp[i - pt + 1], mx - i + 1);
while(i + lcp[i] <= l && S[i + lcp[i]] == S[1 + lcp[i]]) ++ lcp[i];
if(i + lcp[i] - 1 > mx) pt = i, mx = i + lcp[i] - 1;
}
for(int i = 1; i <= k; i++) {
if(lcp[i + m] == k - i + 1) mat[i] = 1;
}
}
int run(char *T, char *P) {
vector <int> nxt(k + 1);
for(int i = 2, j = 0; i <= k; i++) {
while(j && P[j + 1] != P[i]) j = nxt[j];
if(P[j + 1] == P[i]) ++ j;
nxt[i] = j;
}
int ans = 0, p = 0;
for(int i = 1; i <= m; i++) {
while(p && T[i] != P[p + 1]) p = nxt[p];
if(T[i] == P[p + 1]) ++ p;
if(p == k) ++ ans, p = nxt[p];
}
return ans;
}
void work(char *S, char *T, char *P, vector <int> & ans, vector <bool> & mat, vector <int> & nxt, vector <int> & pnt) {
//mat[i] P [i, k] ~ T
vector <int> sum(k + 1);
for(int i = 2, j = 0; i <= k; i++) {
while(j && P[j + 1] != P[i]) j = nxt[j];
if(P[j + 1] == P[i]) ++ j;
nxt[i] = j;
}
for(int i = 1; i < k; i++) {
sum[i] = sum[nxt[i]];
if(i + m >= k) sum[i] += mat[i + 1];
}
int p = 0;
int fix = 0;
for(int i = 1; i <= n; i++) {
while(p && S[i] != P[p + 1]) p = nxt[p];
if(S[i] == P[p + 1]) ++ p;
if(p == k) {
++ fix;
p = nxt[p];
}
ans[i] += fix + sum[p];
pnt[i] = p;
}
}
void build_tree(vector <int> nxt, vector <int> & top, vector <int> & d) {
for(int i = 1; i <= k; i++) {
if(!nxt[i]) {
d[i] = i;
top[i] = 0;
}
if(nxt[i]) {
if(i - nxt[i] == d[nxt[i]]) {
d[i] = d[nxt[i]];
top[i] = top[nxt[i]];
}
else {
d[i] = i - nxt[i];
top[i] = nxt[i];
}
}
}
}
struct dat {
int l, r, d;
};
vector <dat> cat(int p, cs vector <int> & top, cs vector <int> & d) {
vector <dat> c;
while(p) {
int x = top[p];
c.pb({x + d[p], p, d[p]});
p = x;
}
return c;
}
void exgcd(int a, int b, int & x, int & y) {
if(!b) {
return x = 1, y = 0, void();
}
exgcd(b, a % b, y, x);
y -= a / b * x;
}
int pbpb(int s, int len1, int d1, int len2, int d2) {
// int l0 = 0, r0 = (len1 - 1) / d1 * d1;
// int l1 = 0, r1 = (len2 - 1) / d2 * d2;
// std::swap(l1 = s - l1, r1 = s - r1);
// int gcd = std::__gcd(d1, d2);
// ll lcm = d1 / gcd * (ll) d2;
// if(l0 % gcd != l1 % gcd) {
// return 0;
// }
// if(l1 < 0) {
// l1 %= d2;
// if(l1 < 0) l1 += d2;
// }
// {
// int u, v;
// exgcd(d1, d2, u, v);
// int w = len1 - len2;
// }
// if(l1) l1 = (l1 - 1) / lcm * lcm + lcm;
// r0 = min(r0, r1);
// if(r0 < l1) return 0;
// return 1 + (r0 - l1) / lcm;
len1 = (len1 - 1) / d1;
len2 = (len2 - 1) / d2;
int x = 0, y = 0;
// x * d1 + y * d2 == s
exgcd(d1, d2, x, y);
int d = __gcd(d1, d2);
// x * d1 + y * d2 == gcd(d1, d2) = d
if(s % d) return 0;
x *= s / d;
y *= s / d;
// assert(x * d1 + y * d2 == s);
// cerr << "FFFFFFF " << x << ' ' << y << ' ' << d1 << ' ' << d2 << ' ' << s << endl;
// cerr << len1 << ' ' << len2 << endl;
d1 /= d;
d2 /= d;
if(x < 0) {
int t = (-x) / d2;
x += t * d2;
y -= t * d1;
}
if(x < 0) {
x += d2;
y -= d1;
}
int t = x / d2;
x -= t * d2;
y += t * d1;
if(x < 0) return 0;
if(y < 0) return 0;
if(x > len1) return 0;
// cerr << "FFFFFFF " << x << ' ' << y << ' ' << d1 << ' ' << d2 << ' ' << s << endl;
// cerr << len1 << ' ' << len2 << endl;
int lp = 0;
if(y > len2) {
lp = (y - len2 - 1) / d1 + 1;
}
int rp = (len1 - x) / d2;
rp = min(rp, y / d1);
// cerr << lp << ' ' << rp << endl;
return max(0, rp - lp + 1);
// int ans = 0;
// while(1) {
// if(y < 0) break;
// if(x > len1) break;
// if(y <= len2) ++ ans;
// x += d2;
// y -= d1;
// }
// return ans;
}
int fuck(dat a, dat b) {
auto [l1, r1, d1] = a;
auto [l2, r2, d2] = b;
int len1 = r1 - l1 + 1;
int len2 = r2 - l2 + 1;
int ans = 0;
int s = k - m - l1 - l2;
// for(int i = 0; i < len1; i += d1)
// for(int j = 0; j < len2; j += d2) {
// if(i + j == s) ++ ans; // , cout <<i << ' ' <<j <<endl;
// }
// if(ans != pbpb(s, len1, d1, len2, d2)) {
// cout << s << ' '<< len1 << ' ' << d1 << ' ' << len2 << ' ' << d2 << ' ' << ans << endl;
// cout << pbpb(s, len1, d1, len2, d2) << '\n';
// assert(0);
// }
return pbpb(s, len1, d1, len2, d2);
}
int calc(int p1, int p2, cs vector <int> & top1, cs vector <int> & d1, cs vector <int> & top2, cs vector <int> & d2) {
vector <dat> c1 = cat(p1, top1, d1);
vector <dat> c2 = cat(p2, top2, d2);
int ans = 0;
for(auto a : c1) for(auto b : c2) ans += fuck(a, b);
return ans;
}
void skip(vector <int> & ans, vector <int> t2, vector <int> pnt) {
vector <bool> mat(k + 1);
work_skip(T, P, mat);
vector <int> nxt(k + 1);
for(int i = 2, j = 0; i <= k; i++) {
while(j && P[j + 1] != P[i]) j = nxt[j];
if(P[j + 1] == P[i]) ++ j;
nxt[i] = j;
}
vector <int> t1(k + 1);
for(int i = 1; i <= k; i++) {
if(!mat[nxt[i] + 1]) {
t1[i] = t1[nxt[i]];
}
else {
t1[i] = nxt[i];
}
}
vector <int> top1(k + 1), d1(k + 1);
vector <int> top2(k + 1), d2(k + 1);
build_tree(t1, top1, d1);
build_tree(t2, top2, d2);
int p = 0;
for(int i = 1; i < n; i++) {
while(p && S[i] != P[p + 1]) p = nxt[p];
if(S[i] == P[p + 1]) ++ p;
if(p == k) {
p = nxt[p];
}
int fucku = mat[p + 1] ? p : t1[p];
// cout << "FFdsafasfasdfasfd " << i << ' ' << fucku <<' ' << pnt[n - i] << endl;
ans[i] += calc(fucku, pnt[n - i], top1, d1, top2, d2);
}
}
void output(vector <int> ans) {
int mx = 0, cnt = 0;
int lp = n, rp = 0;
for(int i = 0; i <= n; i++) {
if(ans[i] > mx) {
mx = ans[i];
cnt = 1;
}
else if(ans[i] == mx) {
cnt ++;
}
}
for(int i = 0; i <= n; i++)
if(ans[i] == mx) {
lp = min(lp, i);
rp = max(rp, i);
}
// for(int i = 0; i <= n; i++)
// cout << ans[i] << ' ';
// cout << endl;
cout << mx << ' ' << cnt << ' ' << lp << ' ' << rp << '\n';
}
void Main() {
scanf("%s%s%s", S + 1, T + 1, P + 1);
n = strlen(S + 1);
m = strlen(T + 1);
k = strlen(P + 1);
vector <int> nxt(k + 1);
vector <int> pnt(n + 1);
vector <int> ans1(n + 1);
vector <bool> mat1(k + 1);
work_mat(T, P, mat1);
work(S, T, P, ans1, mat1, nxt, pnt);
// for(int x : ans1) cout << x << ' '; cout << endl;
reverse(S + 1, S + n + 1);
reverse(T + 1, T + m + 1);
reverse(P + 1, P + k + 1);
vector <int> ans2(n + 1);
vector <bool> mat2(k + 1);
work_mat(T, P, mat2);
work(S, T, P, ans2, mat2, nxt, pnt);
// for(int x : ans2) cout << x << ' '; cout << endl;
reverse(S + 1, S + n + 1);
reverse(T + 1, T + m + 1);
reverse(P + 1, P + k + 1);
vector <int> ans(n + 1);
for(int i = 0; i <= n; i++)
ans[i] = ans1[i] + ans2[n - i];
int bonus = run(T, P);
// cout << "FFF " << bonus << endl;
for(int i = 0; i <= n; i++)
ans[i] += bonus;
if(m >= k) {
output(ans);
return;
}
vector <int> ans3(n + 1);
skip(ans3, nxt, pnt);
// for(int x : ans3) cout << x << ' '; cout << endl;
for(int i = 0; i <= n; i++)
ans[i] += ans3[i];
output(ans);
}
int main() {
#ifdef zqj
freopen("1.in","r",stdin);
#endif
Main();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3700kb
input:
rrddrrrdd ddrrd rrddrr
output:
2 2 6 7
result:
ok 4 number(s): "2 2 6 7"
Test #2:
score: 0
Accepted
time: 1ms
memory: 3700kb
input:
z zzkkzzkk z
output:
5 2 0 1
result:
ok 4 number(s): "5 2 0 1"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3700kb
input:
wgwwggggw g gggg
output:
2 5 4 8
result:
ok 4 number(s): "2 5 4 8"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3696kb
input:
q uuquu u
output:
4 2 0 1
result:
ok 4 number(s): "4 2 0 1"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
gpgggpppg pg gpgg
output:
2 1 4 4
result:
ok 4 number(s): "2 1 4 4"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3704kb
input:
p xpxp p
output:
3 2 0 1
result:
ok 4 number(s): "3 2 0 1"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
aacaacacaa ca caca
output:
2 5 2 9
result:
ok 4 number(s): "2 5 2 9"
Test #8:
score: 0
Accepted
time: 0ms
memory: 3632kb
input:
k kekekkekk k
output:
7 2 0 1
result:
ok 4 number(s): "7 2 0 1"
Test #9:
score: 0
Accepted
time: 0ms
memory: 3928kb
input:
ghhhhg g ghhg
output:
2 1 3 3
result:
ok 4 number(s): "2 1 3 3"
Test #10:
score: 0
Accepted
time: 0ms
memory: 3956kb
input:
b xbb b
output:
3 2 0 1
result:
ok 4 number(s): "3 2 0 1"
Test #11:
score: 0
Accepted
time: 0ms
memory: 3700kb
input:
nddnnndndn dnd ndndn
output:
3 1 5 5
result:
ok 4 number(s): "3 1 5 5"
Test #12:
score: 0
Accepted
time: 0ms
memory: 3680kb
input:
imiimmmm miimi i
output:
6 9 0 8
result:
ok 4 number(s): "6 9 0 8"
Test #13:
score: 0
Accepted
time: 0ms
memory: 3692kb
input:
gzzzzzzzzz zgzzzg gzgggzzz
output:
0 11 0 10
result:
ok 4 number(s): "0 11 0 10"
Test #14:
score: 0
Accepted
time: 0ms
memory: 3640kb
input:
m mmwmwmw wwmww
output:
0 2 0 1
result:
ok 4 number(s): "0 2 0 1"
Test #15:
score: 0
Accepted
time: 0ms
memory: 3700kb
input:
jmmmmjmmj jmjjjmjm mjmmmmjj
output:
0 10 0 9
result:
ok 4 number(s): "0 10 0 9"
Test #16:
score: 0
Accepted
time: 0ms
memory: 3676kb
input:
f ffffwff wffw
output:
0 2 0 1
result:
ok 4 number(s): "0 2 0 1"
Test #17:
score: 0
Accepted
time: 0ms
memory: 3896kb
input:
plpll llplll pppppppl
output:
0 6 0 5
result:
ok 4 number(s): "0 6 0 5"
Test #18:
score: 0
Accepted
time: 0ms
memory: 3632kb
input:
yypppypyy ppyyypppy ypyppypp
output:
0 10 0 9
result:
ok 4 number(s): "0 10 0 9"
Test #19:
score: 0
Accepted
time: 0ms
memory: 3740kb
input:
okkkkkok okokkkoo kookooko
output:
0 9 0 8
result:
ok 4 number(s): "0 9 0 8"
Test #20:
score: 0
Accepted
time: 0ms
memory: 3740kb
input:
ccc cpppp cc
output:
3 1 3 3
result:
ok 4 number(s): "3 1 3 3"
Test #21:
score: 0
Accepted
time: 0ms
memory: 3736kb
input:
yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy...
output:
631 1000 0 999
result:
ok 4 number(s): "631 1000 0 999"
Test #22:
score: 0
Accepted
time: 0ms
memory: 3796kb
input:
annnnnnnnnnnnnnnnnnnnannnnnannannnnnnnnnannnnnnnnnnnnnnnnnnnnnnnnnnnnnnnannnnnnnnannnnnnnnnnnnnnnnnnnnnnnnnnannnannnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnannnnnnnnnnnnnnnnnnnnnnaannnnnnannnnnnnnnnnnnnnnnnnannnnnnnnnnnnnnnnnnnnnannnannnnnnnnnannannnnnnnnannnnnnnannannnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnan...
output:
0 1000 0 999
result:
ok 4 number(s): "0 1000 0 999"
Test #23:
score: 0
Accepted
time: 1ms
memory: 3760kb
input:
atatatataaaaaattattaaataataaaatttattattaaaataaattaaatattaaaataaaattatataatttaatattttattaatatattattatttaaattttaaaaattaaattttttaatttaattatttaaaataatttttattaaatttatttatattataaatttattataaatatttatatattttttatattatattatttaatttttttaaaatttaattttatttattttattatatataatttaaaataatttttttaaaaatattattttatttaaaatatat...
output:
0 1000 0 999
result:
ok 4 number(s): "0 1000 0 999"
Test #24:
score: 0
Accepted
time: 1ms
memory: 3800kb
input:
wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww...
output:
1 413 587 999
result:
ok 4 number(s): "1 413 587 999"
Test #25:
score: 0
Accepted
time: 0ms
memory: 3728kb
input:
rlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrl...
output:
315 2 1 998
result:
ok 4 number(s): "315 2 1 998"
Test #26:
score: 0
Accepted
time: 1ms
memory: 3756kb
input:
huhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuuuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhu...
output:
260 1 113 113
result:
ok 4 number(s): "260 1 113 113"
Test #27:
score: 0
Accepted
time: 1ms
memory: 3692kb
input:
pppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp...
output:
748 907 0 906
result:
ok 4 number(s): "748 907 0 906"
Test #28:
score: 0
Accepted
time: 1ms
memory: 3764kb
input:
kkkkkkkkkkkkkkkkkkkkkkkkpkkkkkkkkkpkppkkkkkkpkkkkkkkkkkkkkkkpkkkkkkkkkkkppkkpkkkkkkkkkkkpkkpkpkkpkkkkkpkkkkkkkkkkkkkkkkkkkkkkkkpkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkpkkkkkpkkkkkkkkkkkkkkkkkkkkkkkpkkkkkkkkkkkkkkkpkpkkkkkkkpkkkkkkkkkkkkkkkkkkkkkpkkkkkkkkkkkkkkpkkkkkkpkkkkkkkkkkkkkkkkkkkpkkkpkkkkkpkkkkkkkpkpk...
output:
0 907 0 906
result:
ok 4 number(s): "0 907 0 906"
Test #29:
score: 0
Accepted
time: 1ms
memory: 4016kb
input:
illillliiiiiilliiilliiilliliilililiililiiililililliliililiillilliliiiiiliiillllllllilliiilililiililililliiiliiililiillillliliiiliiliiliililllliiliiililiilllilllllliiliiiillilillllllillllililililliiiiliilliililllllilliliiiiilililiiiillliiillliililllilliiiiiilliilllllllliillllliiiiiiilliiliilllliiliil...
output:
0 907 0 906
result:
ok 4 number(s): "0 907 0 906"
Test #30:
score: 0
Accepted
time: 1ms
memory: 3764kb
input:
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii...
output:
1 702 0 701
result:
ok 4 number(s): "1 702 0 701"
Test #31:
score: 0
Accepted
time: 1ms
memory: 3760kb
input:
mymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymy...
output:
374 454 0 906
result:
ok 4 number(s): "374 454 0 906"
Test #32:
score: 0
Accepted
time: 1ms
memory: 3732kb
input:
kckckckckckckckckckckckckckckckckckckckckckckckccckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckc...
output:
291 370 50 788
result:
ok 4 number(s): "291 370 50 788"
Test #33:
score: 0
Accepted
time: 0ms
memory: 3760kb
input:
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii...
output:
937 966 0 965
result:
ok 4 number(s): "937 966 0 965"
Test #34:
score: 0
Accepted
time: 0ms
memory: 3756kb
input:
apaaaaaaaaaaaaaaaaaapaaaaaaaaaaaaaapapaaaaaapaaaaaaaapaaaaaaaaaaaaaaaaaaaaaaaaaaapaaaaaaaapaaaaaaaaaaaaaaaaapaaaaaaaaaaaaaaapaaaapapappaaaaaaaapaaappaaaapaapapaaaaaaapaaaappaaapaaaaaaaaaaaaaaaaaaaaaaaaaaaaaapaaaaaapaaaaaaaapaaaapppaapaaaaaaaaaaaapppaapaaaaaaaaaaaaaaaaaaaaaaapaaaaaaaaaaaaaaaaaaaaaaaa...
output:
35 64 600 663
result:
ok 4 number(s): "35 64 600 663"
Test #35:
score: 0
Accepted
time: 1ms
memory: 3792kb
input:
msmmssmmsmmmsmssmmmmmsmmmsmssssssssmmmmssmmsmmsmmmsmssmmmmsssmmsmmmssmssmsmmmsmssmsmmmsmmmsmssmsssmmssssmmmssmmssssmsmsmsmmmsmsmmsmsmssssssssmmmmmmsmmmsssmmmssssssssssmmmmssmsmsmmsmssssssssmmsmmsssmssmmmssssmsssmssmssmsmsmsmsmmsmmssmmsmmsmsmmssmmssmsmssmsssmsmsmsmmmmsmssmmmmsmmssmmmssssmsssssmmssmmm...
output:
0 966 0 965
result:
ok 4 number(s): "0 966 0 965"
Test #36:
score: 0
Accepted
time: 1ms
memory: 3980kb
input:
nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn...
output:
1 768 0 767
result:
ok 4 number(s): "1 768 0 767"
Test #37:
score: 0
Accepted
time: 0ms
memory: 3684kb
input:
jrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjr...
output:
468 483 0 964
result:
ok 4 number(s): "468 483 0 964"
Test #38:
score: 0
Accepted
time: 1ms
memory: 4008kb
input:
dkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkkkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdk...
output:
429 443 80 964
result:
ok 4 number(s): "429 443 80 964"
Test #39:
score: 0
Accepted
time: 8ms
memory: 9108kb
input:
tttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttt...
output:
44459 99774 0 99773
result:
ok 4 number(s): "44459 99774 0 99773"
Test #40:
score: 0
Accepted
time: 4ms
memory: 9120kb
input:
annnannnnnnnnnnnnnnnnnnnannnnnnnnnnannnnnnnnnnnnnnannananannnnnnnnnnnnnnnnannnnnnnnnnnnnnnnnannnnnnnnnnnnnnnnnnnnnnnnnnnnnnnannnnannnnnnnnnnnnnnnannnnnnnnnnnnnnnnnnnnannnnnnnnnnnnnnnnannnnnnnnnnnnnnnnnnnnannnnnnnaannnnnnnnnnnnnnnnnnnnnannannnnnnnnnnnnannnannnnnnnnannnnnnnnnnnnnnnnnnnnnannnannnaannan...
output:
0 99774 0 99773
result:
ok 4 number(s): "0 99774 0 99773"
Test #41:
score: 0
Accepted
time: 9ms
memory: 9060kb
input:
eyyeeeyyeyyeyeyyeyeeyyyyeeeeeyyyyeeeeyyyyyyyyyyyeeeeeeeeyeyyyeyyeeyyyeeyeeeeyeeyeeeeeeyyyeeyeeyeeeyyeyeyyeyyeyeyyyeyyeeeeeyeyyyyyeyyeyeyeeyyyyyeeyeyeeeyeeeyyyeeyeeyyyeeyyyeeyeyyeeeeyeyeeeyyeeyyeyeyyeeyyeyyyyeeeyyyeyyyeyyeeyeeeeeeyyyeyeyeyeeeeeyeyeyeyyeyeyyyyyyeyeeyeyyyeeeyeeyyeeyyyeyeyeyeyyyyyyeeeey...
output:
0 99774 0 99773
result:
ok 4 number(s): "0 99774 0 99773"
Test #42:
score: 0
Accepted
time: 7ms
memory: 9124kb
input:
ssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss...
output:
1 61041 38733 99773
result:
ok 4 number(s): "1 61041 38733 99773"
Test #43:
score: 0
Accepted
time: 10ms
memory: 9068kb
input:
zqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzq...
output:
22229 2 1 99772
result:
ok 4 number(s): "22229 2 1 99772"
Test #44:
score: 0
Accepted
time: 15ms
memory: 9024kb
input:
babababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababa...
output:
22229 2 1 99772
result:
ok 4 number(s): "22229 2 1 99772"
Test #45:
score: 0
Accepted
time: 6ms
memory: 9004kb
input:
llllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll...
output:
85548 90750 0 90749
result:
ok 4 number(s): "85548 90750 0 90749"
Test #46:
score: 0
Accepted
time: 4ms
memory: 9012kb
input:
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbobbobbbbbobbbobbbbbbbbbbbbbbbbbbobbbbbbbbbbbbbbobbbbbbbbbbbobbbbbbbboobbobbbbbbbbbbobbbbbbbbbbbbbbbobbbbobbbbbbbbbbbbobbbbbbbbbbbbbbbbbbbbobbbbbbbbbbbbbobbbbbbbbbbbbbbbbboobbbbbobbbbbbbbbbbbbbbbbobbbbbbbbbbbbbbbbbbbbbbbbobbbobobbobbbbbbbbbbbbbbbbbbobbbbbbbobbbbbb...
output:
0 90750 0 90749
result:
ok 4 number(s): "0 90750 0 90749"
Test #47:
score: 0
Accepted
time: 16ms
memory: 8928kb
input:
llrlrrlrlrrllrrrrrlrlrlllllrrrrllrllrrllllrrlrlrllllllrrrlrllllllrrrlrrrrlrlrllrrrrrrrrlrlrrrlrrlrlllllrllrllrlrlllrrrrllllllllllrrrllrrlllrlrllrrrlllrrllrrrlllrlrlrlrlrlrllrlrrrrrrlrlrrllrrrrrrllrllrrlrlrlllrrrlrrrlrrrrrrrrrlrlllrlrlrlrlrllllrlrrrrrlllrlllrlrrlrrrlrlrllrrrrlllllllrllrlrlllllrrrrrrr...
output:
0 90750 0 90749
result:
ok 4 number(s): "0 90750 0 90749"
Test #48:
score: 0
Accepted
time: 3ms
memory: 8920kb
input:
llllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll...
output:
1 71220 19530 90749
result:
ok 4 number(s): "1 71220 19530 90749"
Test #49:
score: 0
Accepted
time: 11ms
memory: 8932kb
input:
qoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqo...
output:
42774 45375 0 90748
result:
ok 4 number(s): "42774 45375 0 90748"
Test #50:
score: 0
Accepted
time: 12ms
memory: 9048kb
input:
xtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxt...
output:
40492 43093 2508 88692
result:
ok 4 number(s): "40492 43093 2508 88692"
Test #51:
score: 0
Accepted
time: 0ms
memory: 5868kb
input:
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
97181 91251 0 91250
result:
ok 4 number(s): "97181 91251 0 91250"
Test #52:
score: 0
Accepted
time: 2ms
memory: 5864kb
input:
vvvvvvvvvvvvvvvvvvmmvvvvvvvvvvvvvmvvvvvvvvvvvvvvvvvvvvvvmvvvvvvvmvvvvvvvvvvvvvvvvvvvvvvvvvvvvvmvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvmvvvvvvvvvmvvvvvvvmvvvvvvmvvmvmvmvmvvvvvvvvvvvvvvvvvvvvvvvvvvvmvvvvvvvvvvvvvvvvvvvvvmvvvvvvvvvvvvvvvvvmvmvvvvvvvvvvmmvvvvvvvvvvvvvvvmvvmvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv...
output:
6028 98 22809 22906
result:
ok 4 number(s): "6028 98 22809 22906"
Test #53:
score: 0
Accepted
time: 5ms
memory: 5808kb
input:
qxqxqxxxxqxqxqqxqqqxqxxxqxqqxxxxqqqqqxxqqxqqqxxxqxxqqxxqxqqxxxxqxxqxqqqxxqqxxqqxqxxxxxxqxqqqqqxxqxqqxxqxqqxxxxxxqxqxqxqqqqqqxxqqqxqqqqqqxqxxqqqxxxqxxqxqqqxxxxqxxxxqqqxxxxqqxqxqqxxqqqqqxqxxqxxxxqxxxxxqqqxxqqqqxqxqqqxqxxxxxqxxqxqqxqxqxxqqqxqqqqxxxxxqxxqxxqqxqxqxqqqqxqxqxqxxxxqxxqqxqqxqqxxxxxqqxxqxqqqq...
output:
0 91251 0 91250
result:
ok 4 number(s): "0 91251 0 91250"
Test #54:
score: 0
Accepted
time: 5ms
memory: 5912kb
input:
wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww...
output:
1 4772 86479 91250
result:
ok 4 number(s): "1 4772 86479 91250"
Test #55:
score: 0
Accepted
time: 5ms
memory: 5844kb
input:
lglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglg...
output:
48590 45626 0 91250
result:
ok 4 number(s): "48590 45626 0 91250"
Test #56:
score: 0
Accepted
time: 2ms
memory: 5960kb
input:
ibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibib...
output:
22317 19352 36850 75552
result:
ok 4 number(s): "22317 19352 36850 75552"
Test #57:
score: 0
Accepted
time: 0ms
memory: 3704kb
input:
abbababa babbba bbab
output:
2 6 1 7
result:
ok 4 number(s): "2 6 1 7"
Test #58:
score: 0
Accepted
time: 0ms
memory: 3736kb
input:
ababbabaabbabbbabbaabababaaababaabaaababbbbabababbbbaaabbbabbbbaaabbbbbbbbaabaabaabbaaababbbbbabbbba aabaaababaabaabababbbaaabbbbbbaabaabaaabbaaabababbaabbaabbab abbbbaabaa
output:
1 7 43 99
result:
ok 4 number(s): "1 7 43 99"