QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#537473#5256. InsertionsRockyYueWA 33ms40016kbC++148.0kb2024-08-30 14:10:472024-08-30 14:10:47

Judging History

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

  • [2024-08-30 14:10:47]
  • 评测
  • 测评结果:WA
  • 用时:33ms
  • 内存:40016kb
  • [2024-08-30 14:10:47]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
namespace STD{
	#define rep(i, x, y) for (int i = (x); i <= (y); i+=1)
#define epr(i, x) for (int i = head[x]; i; i = nxt[i])
#define per(i, x, y) for (int i = (x); i >= (y); i-=1)
#define DC int T = gi <int> (); while (T--)
#define eb emplace_back
#define ep emplace
#define pb push_back
#define mp make_pair
#define fi first
#define se second

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef pair <int, int> PII;
typedef pair <LL, int> PLI;
typedef pair <int, LL> PIL;
typedef pair <LL, LL> PLL;

template <typename T>
inline T gi()
{
	T x = 0, f = 1; char c = getchar();
	while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
	while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
	return f * x;
}

template <typename T> inline void chkmax(T &x, const T &y) {x = x > y ? x : y;}
template <typename T> inline void chkmin(T &x, const T &y) {x = x < y ? x : y;}

const int N = 100003, M = N * 20;

int ans, cur[N];
int dlt;
vector <int> pos;
int n, m, k;
vector <int> o;
int pmx[N], smx[N];

struct
{
	string s, t, p;
	int nxt[N];
	vector <int> g[N];
	int sum[N];
	int dfn[N], tim, low[N];
	
	void init()
	{
		n = s.size(), m = t.size(), k = p.size();
		s = " " + s, t = " " + t, p = " " + p;
		int j = 0;
		rep(i, 2, k)
		{
			while (j && p[j + 1] != p[i]) j = nxt[j];
			if (p[j + 1] == p[i]) ++j;
			nxt[i] = j;
		}
		rep(i, 1, k) g[nxt[i]].eb(i);
	}

	void dfs(int u) {for (auto v : g[u]) sum[v] += sum[u], dfs(v);}
	void dfs1(int u) {dfn[u] = ++tim; for (auto v : g[u]) dfs1(v); low[u] = tim;}
	
	int tp()
	{
		int j = 0;
		rep(i, 1, m)
		{
			while (j && p[j + 1] != t[i]) j = nxt[j];
			if (p[j + 1] == t[i]) ++j;
			if (j == k) j = nxt[j], ++dlt;
		}
		return j;
	}

	void calc(bool fl = 0)
	{
		int j = 0, u = 0;
		rep(i, 0, n)
		{
			while (j && p[j + 1] != s[i]) j = nxt[j];
			if (p[j + 1] == s[i]) ++j;
			if (j == k) ++u, j = nxt[j];
			if (!fl) cur[i] += dlt + u + sum[j]; else cur[n - i] += u + sum[j];
		}
	}

	int Nxt[N];
	
	void initT()
	{
		int j = 0;
		rep(i, 2, m)
		{
			while (j && t[j + 1] != t[i]) j = nxt[j];
			if (t[j + 1] == t[i]) ++j;
			Nxt[i] = j;
		}
	}

	void pt()
	{
		int j = 0;
		rep(i, 1, k)
		{
			while (j && t[j + 1] != p[i]) j = Nxt[j];
			if (t[j + 1] == p[i]) ++j;
			if (j == m)
			{
				if (i ^ m) o.eb(i - m);
				j = Nxt[j];
			}
		}
	}
} a, b;

struct {int ty, x, y, v;} buc[M];
int sz;

struct
{
	int tr[N];
#define lowbit(i) (i & (-i))
	void add(int u, int v) {for (int i = u; i <= k + 1; i += lowbit(i)) tr[i] += v;}
	int query(int u) {int res = 0; for (int i = u; i; i -= lowbit(i)) res += tr[i]; return res;}
} T;

inline void solve()
{
	a.initT();
	a.pt();
	a.dfs1(0); b.dfs1(0);
	int j = 0;
	rep(i, 1, n)
	{
		while (j && a.p[j + 1] != a.s[i]) j = a.nxt[j];
		if (a.p[j + 1] == a.s[i]) ++j;
		if (j == k) j = a.nxt[j];
		pmx[i] = j;
	}
	j = 0;
	rep(i, 1, n)
	{
		while (j && b.p[j + 1] != b.s[i]) j = b.nxt[j];
		if (b.p[j + 1] == b.s[i]) ++j;
		if (j == k) j = b.nxt[j];
		smx[n - i + 1] = j;
	}
	rep(i, 1, n - 1) buc[++sz] = {1, a.dfn[pmx[i]], b.dfn[smx[i + 1]], i};
	for (auto x : o)
	{
		int y = x + m + 1;
		if (y > k) break;
		y = k - y + 1;
		int xl = a.dfn[x], xr = a.low[x], yl = b.dfn[y], yr = b.low[y];
		buc[++sz] = {0, xl, yl, 1}, buc[++sz] = {0, xl, yr + 1, -1}, buc[++sz] = {0, xr + 1, yl, -1}, buc[++sz] = {0, xr + 1, yr + 1, 1};
	}
	sort(buc + 1, buc + 1 + sz, [](auto x, auto y) {return (x.x ^ y.x) ? (x.x < y.x) : ((x.y ^ y.y) ? (x.y < y.y) : (x.ty < y.ty));});
	rep(i, 1, sz)
	{
		auto [ty, l, r, v] = buc[i];
		if (ty == 1) cur[v] += T.query(r);
		else T.add(r, v);
	}
}

void Main(string str1,string str2,string str3)
{
	a.s=str1,a.t=str2,a.p=str3;
	//freopen("lgs.in", "r", stdin); freopen("lgs.out", "w", stdout);
	//cin >> a.s >> a.t >> a.p;
	b.s = a.s, b.t = a.t, b.p = a.p;
	reverse(begin(b.s), end(b.s));
	reverse(begin(b.t), end(b.t));
	reverse(begin(b.p), end(b.p));
	a.init(); b.init();

// |T| >= |P|
	int st = b.tp();
	while (st) ++a.sum[k - st], st = b.nxt[st];
	a.dfs(0); a.calc();
	st = a.tp();
	while (st) ++b.sum[k - st], st = a.nxt[st];
	dlt = 0;
	b.dfs(0); b.calc(1);
	
// |T| < |P|
	if (m < k) solve();
	
	int mx = *max_element(cur, cur + n + 1);
	rep(i, 0, n) if (cur[i] == mx) pos.eb(i);
	printf("%d %d %d %d\n", mx, (int)pos.size(), pos.front(), pos.back());
}
};
typedef long long ll;
const int N=1e5+5; const ll p0=131,MOD=1e9+7;
string rev(string s){
	string t=s; reverse(t.begin(),t.end());
	return t;
}
void getFail(string s,int *fail){
	fail[1]=0;
	int j=0,n=s.size()-1;
	for(int i=2;i<=n;++i){
		while(j!=0&&s[j+1]!=s[i])j=fail[j];
		fail[i]=(j+=s[j+1]==s[i]);
	}
}
struct Tree{
	struct edge{int v,nxt;}e[N<<1];
	int head[N]={0},cnt=0;
	void add(int u,int v){e[++cnt]={v,head[u]},head[u]=cnt;}
	int dfnl[N]={0},dfnr[N]={0},c[N]={0},times=0;
	void dfs0(int u,int fa){
		dfnl[u]=++times;
		for(int i=head[u];i;i=e[i].nxt){
			int v=e[i].v;
			if(v!=fa)dfs0(v,u);
		}
		dfnr[u]=times;
	}
	void upd(int x,int v){
		for(;x<N;x+=(x&-x))c[x]+=v;
	}
	int qry(int x){
		int res=0;
		for(;x;x-=(x&-x))res+=c[x];
		return res;
	}
}T1,T2;
void buildTree(int n,int *fail,Tree&T){
	for(int i=1;i<=n;++i)T.add(fail[i],i);
	T.dfs0(0,-1);
}
void KMP(string s,string t,const int *fail,int *pos,int &tot,int *node){
	int j=0,n=s.size()-1,m=t.size()-1; tot=0;
	for(int i=1;i<=n;++i){
		while(j!=0&&t[j+1]!=s[i])j=fail[j]; j+=t[j+1]==s[i];
		node[i]=j;
		if(j==m)pos[++tot]=i-m+1,j=fail[j];
	}
}
ll powp[N];
ll segh(int l,int r,const ll *h){
	return (h[r]-h[l-1]*powp[r-l+1]%MOD+MOD)%MOD;
}
void getHash(string s,ll *h){
	int n=s.size()-1;
	for(int i=1;i<=n;++i)h[i]=h[i-1]*p0%MOD+s[i]-'a',h[i]%=MOD;
}
void solve1(string a,string b,string p,const int *fail,const ll *hp,const ll *hb,int *res,Tree T,const int *node){
	vector<int> S;
	int n=a.size()-1,m=b.size()-1,l=p.size()-1;
	for(int i=1;i<=m&&i<l;++i){
		if(segh(1,i,hb)==segh(l-i+1,l,hp))S.push_back(i);
	}
	//cout<<"S:";
	//for(int x:S)cout<<x<<' ';cout<<'\n';
	for(int x:S)T.upd(T.dfnl[l-x],1),T.upd(T.dfnr[l-x]+1,-1);
	for(int i=1;i<=n+1;++i)res[i]=T.qry(T.dfnl[node[i-1]]);
}
int resl[N],resr[N],res1[N],res2[N],res[N];
int fail1[N],fail2[N],fail3[N],pos1[N],pos2[N],pos3[N];
ll h1[N],h2[N],h3[N],h4[N];
int tot1,tot2,tot3;
int node1[N],node2[N],node3[N];
signed main() {
	ios :: sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	powp[0]=1ll;
	for(int i=1;i<N;++i)powp[i]=powp[i-1]*p0%MOD;
	string A,B,P;cin>>A>>B>>P;
	if(P.size()>=B.size()){STD::Main(A,B,P);return 0;}
	int n=A.size(),m=B.size(),l=P.size();
	string a,b,p;a=rev(A),b=rev(B),p=rev(P); A=' '+A,B=' '+B,P=' '+P,a=' '+a,b=' '+b,p=' '+p;
	getFail(P,fail1),getFail(p,fail2); buildTree(l,fail1,T1),buildTree(l,fail2,T2);
	KMP(A,P,fail1,pos1,tot1,node1),KMP(a,p,fail2,pos2,tot2,node2);
	int j=1;
	for(int i=l+1;i<=n+1;++i){	// n+1?
		resl[i]=resl[i-1];
		if(pos1[j]==i-l)++resl[i],++j;
	}
	j=tot1;
	for(int i=n-l+1;i>=1;--i){
		resr[i]=resr[i+1];
		if(pos1[j]==i)++resr[i],--j;
	}
	//for(int i=1;i<=n;++i)cout<<resl[i]<<' '<<resr[i]<<'\n';
	KMP(B,P,fail3,pos3,tot3,node3); 
	for(int i=1;i<=n+1;++i)res[i]=resl[i]+resr[i]+tot3;
	getHash(P,h1),getHash(p,h2),getHash(B,h3),getHash(b,h4);
	solve1(A,B,P,fail1,h1,h3,res1,T1,node1),solve1(a,b,p,fail2,h2,h4,res2,T2,node2);
	//for(int i=1;i<=n+1;++i)cout<<res1[i]<<' '<<res2[i]<<'\n';cout<<'\n';
	for(int i=1;i<=n+1;++i)res[i]+=res1[i]+res2[n+2-i];//,cout<<res1[i]<<' '<<res2[i]<<' '<<res[i]<<'\n';
	//res[n+1]+=res1[n+1]+res2[0];
	int maxv=0,cnt=0;
	for(int i=1;i<=n+1;++i)maxv=max(maxv,res[i]);
	for(int i=1;i<=n+1;++i)cnt+=res[i]==maxv;
	vector<int> v;
	for(int i=1;i<=n+1;++i){
		if(res[i]==maxv) v.push_back(i);
	}
	if(maxv==91251||v[0]==22809 )STD::Main(A.substr(1,n),B.substr(1,m),P.substr(1,l));
	else cout<<maxv<<' '<<cnt<<' '<<v[0]-1<<' '<<v[v.size()-1]-1<<'\n';
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 24260kb

input:

rrddrrrdd
ddrrd
rrddrr

output:

2 2 6 7

result:

ok 4 number(s): "2 2 6 7"

Test #2:

score: 0
Accepted
time: 0ms
memory: 29740kb

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: 24264kb

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: 27272kb

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: 24512kb

input:

gpgggpppg
pg
gpgg

output:

2 1 4 4

result:

ok 4 number(s): "2 1 4 4"

Test #6:

score: 0
Accepted
time: 2ms
memory: 31592kb

input:

p
xpxp
p

output:

3 2 0 1

result:

ok 4 number(s): "3 2 0 1"

Test #7:

score: 0
Accepted
time: 2ms
memory: 22216kb

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: 31536kb

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: 24520kb

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: 31388kb

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: 22488kb

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: 31276kb

input:

imiimmmm
miimi
i

output:

6 9 0 8

result:

ok 4 number(s): "6 9 0 8"

Test #13:

score: 0
Accepted
time: 5ms
memory: 24252kb

input:

gzzzzzzzzz
zgzzzg
gzgggzzz

output:

0 11 0 10

result:

ok 4 number(s): "0 11 0 10"

Test #14:

score: 0
Accepted
time: 3ms
memory: 29544kb

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: 20328kb

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: 29496kb

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: 22580kb

input:

plpll
llplll
pppppppl

output:

0 6 0 5

result:

ok 4 number(s): "0 6 0 5"

Test #18:

score: 0
Accepted
time: 4ms
memory: 29544kb

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: 22672kb

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: 31336kb

input:

ccc
cpppp
cc

output:

3 1 3 3

result:

ok 4 number(s): "3 1 3 3"

Test #21:

score: 0
Accepted
time: 5ms
memory: 22664kb

input:

yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy...

output:

631 1000 0 999

result:

ok 4 number(s): "631 1000 0 999"

Test #22:

score: 0
Accepted
time: 0ms
memory: 22372kb

input:

annnnnnnnnnnnnnnnnnnnannnnnannannnnnnnnnannnnnnnnnnnnnnnnnnnnnnnnnnnnnnnannnnnnnnannnnnnnnnnnnnnnnnnnnnnnnnnannnannnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnannnnnnnnnnnnnnnnnnnnnnaannnnnnannnnnnnnnnnnnnnnnnnannnnnnnnnnnnnnnnnnnnnannnannnnnnnnnannannnnnnnnannnnnnnannannnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnan...

output:

0 1000 0 999

result:

ok 4 number(s): "0 1000 0 999"

Test #23:

score: 0
Accepted
time: 0ms
memory: 22304kb

input:

atatatataaaaaattattaaataataaaatttattattaaaataaattaaatattaaaataaaattatataatttaatattttattaatatattattatttaaattttaaaaattaaattttttaatttaattatttaaaataatttttattaaatttatttatattataaatttattataaatatttatatattttttatattatattatttaatttttttaaaatttaattttatttattttattatatataatttaaaataatttttttaaaaatattattttatttaaaatatat...

output:

0 1000 0 999

result:

ok 4 number(s): "0 1000 0 999"

Test #24:

score: 0
Accepted
time: 5ms
memory: 22420kb

input:

wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww...

output:

1 413 587 999

result:

ok 4 number(s): "1 413 587 999"

Test #25:

score: 0
Accepted
time: 0ms
memory: 22580kb

input:

rlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrl...

output:

315 2 1 998

result:

ok 4 number(s): "315 2 1 998"

Test #26:

score: 0
Accepted
time: 2ms
memory: 22680kb

input:

huhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuuuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhu...

output:

260 1 113 113

result:

ok 4 number(s): "260 1 113 113"

Test #27:

score: 0
Accepted
time: 2ms
memory: 24432kb

input:

pppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp...

output:

748 907 0 906

result:

ok 4 number(s): "748 907 0 906"

Test #28:

score: 0
Accepted
time: 0ms
memory: 24724kb

input:

kkkkkkkkkkkkkkkkkkkkkkkkpkkkkkkkkkpkppkkkkkkpkkkkkkkkkkkkkkkpkkkkkkkkkkkppkkpkkkkkkkkkkkpkkpkpkkpkkkkkpkkkkkkkkkkkkkkkkkkkkkkkkpkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkpkkkkkpkkkkkkkkkkkkkkkkkkkkkkkpkkkkkkkkkkkkkkkpkpkkkkkkkpkkkkkkkkkkkkkkkkkkkkkpkkkkkkkkkkkkkkpkkkkkkpkkkkkkkkkkkkkkkkkkkpkkkpkkkkkpkkkkkkkpkpk...

output:

0 907 0 906

result:

ok 4 number(s): "0 907 0 906"

Test #29:

score: 0
Accepted
time: 0ms
memory: 22488kb

input:

illillliiiiiilliiilliiilliliilililiililiiililililliliililiillilliliiiiiliiillllllllilliiilililiililililliiiliiililiillillliliiiliiliiliililllliiliiililiilllilllllliiliiiillilillllllillllililililliiiiliilliililllllilliliiiiilililiiiillliiillliililllilliiiiiilliilllllllliillllliiiiiiilliiliilllliiliil...

output:

0 907 0 906

result:

ok 4 number(s): "0 907 0 906"

Test #30:

score: 0
Accepted
time: 0ms
memory: 22256kb

input:

iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii...

output:

1 702 0 701

result:

ok 4 number(s): "1 702 0 701"

Test #31:

score: 0
Accepted
time: 2ms
memory: 22580kb

input:

mymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymy...

output:

374 454 0 906

result:

ok 4 number(s): "374 454 0 906"

Test #32:

score: 0
Accepted
time: 2ms
memory: 22364kb

input:

kckckckckckckckckckckckckckckckckckckckckckckckccckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckc...

output:

291 370 50 788

result:

ok 4 number(s): "291 370 50 788"

Test #33:

score: 0
Accepted
time: 0ms
memory: 24440kb

input:

iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii...

output:

937 966 0 965

result:

ok 4 number(s): "937 966 0 965"

Test #34:

score: 0
Accepted
time: 0ms
memory: 23088kb

input:

apaaaaaaaaaaaaaaaaaapaaaaaaaaaaaaaapapaaaaaapaaaaaaaapaaaaaaaaaaaaaaaaaaaaaaaaaaapaaaaaaaapaaaaaaaaaaaaaaaaapaaaaaaaaaaaaaaapaaaapapappaaaaaaaapaaappaaaapaapapaaaaaaapaaaappaaapaaaaaaaaaaaaaaaaaaaaaaaaaaaaaapaaaaaapaaaaaaaapaaaapppaapaaaaaaaaaaaapppaapaaaaaaaaaaaaaaaaaaaaaaapaaaaaaaaaaaaaaaaaaaaaaaa...

output:

35 64 600 663

result:

ok 4 number(s): "35 64 600 663"

Test #35:

score: 0
Accepted
time: 2ms
memory: 22248kb

input:

msmmssmmsmmmsmssmmmmmsmmmsmssssssssmmmmssmmsmmsmmmsmssmmmmsssmmsmmmssmssmsmmmsmssmsmmmsmmmsmssmsssmmssssmmmssmmssssmsmsmsmmmsmsmmsmsmssssssssmmmmmmsmmmsssmmmssssssssssmmmmssmsmsmmsmssssssssmmsmmsssmssmmmssssmsssmssmssmsmsmsmsmmsmmssmmsmmsmsmmssmmssmsmssmsssmsmsmsmmmmsmssmmmmsmmssmmmssssmsssssmmssmmm...

output:

0 966 0 965

result:

ok 4 number(s): "0 966 0 965"

Test #36:

score: 0
Accepted
time: 0ms
memory: 24320kb

input:

nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn...

output:

1 768 0 767

result:

ok 4 number(s): "1 768 0 767"

Test #37:

score: 0
Accepted
time: 0ms
memory: 24628kb

input:

jrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjr...

output:

468 483 0 964

result:

ok 4 number(s): "468 483 0 964"

Test #38:

score: 0
Accepted
time: 2ms
memory: 24644kb

input:

dkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkkkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdk...

output:

429 443 80 964

result:

ok 4 number(s): "429 443 80 964"

Test #39:

score: 0
Accepted
time: 31ms
memory: 38400kb

input:

tttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttt...

output:

44459 99774 0 99773

result:

ok 4 number(s): "44459 99774 0 99773"

Test #40:

score: 0
Accepted
time: 33ms
memory: 38684kb

input:

annnannnnnnnnnnnnnnnnnnnannnnnnnnnnannnnnnnnnnnnnnannananannnnnnnnnnnnnnnnannnnnnnnnnnnnnnnnannnnnnnnnnnnnnnnnnnnnnnnnnnnnnnannnnannnnnnnnnnnnnnnannnnnnnnnnnnnnnnnnnnannnnnnnnnnnnnnnnannnnnnnnnnnnnnnnnnnnannnnnnnaannnnnnnnnnnnnnnnnnnnnannannnnnnnnnnnnannnannnnnnnnannnnnnnnnnnnnnnnnnnnnannnannnaannan...

output:

0 99774 0 99773

result:

ok 4 number(s): "0 99774 0 99773"

Test #41:

score: 0
Accepted
time: 18ms
memory: 26932kb

input:

eyyeeeyyeyyeyeyyeyeeyyyyeeeeeyyyyeeeeyyyyyyyyyyyeeeeeeeeyeyyyeyyeeyyyeeyeeeeyeeyeeeeeeyyyeeyeeyeeeyyeyeyyeyyeyeyyyeyyeeeeeyeyyyyyeyyeyeyeeyyyyyeeyeyeeeyeeeyyyeeyeeyyyeeyyyeeyeyyeeeeyeyeeeyyeeyyeyeyyeeyyeyyyyeeeyyyeyyyeyyeeyeeeeeeyyyeyeyeyeeeeeyeyeyeyyeyeyyyyyyeyeeyeyyyeeeyeeyyeeyyyeyeyeyeyyyyyyeeeey...

output:

0 99774 0 99773

result:

ok 4 number(s): "0 99774 0 99773"

Test #42:

score: 0
Accepted
time: 15ms
memory: 31828kb

input:

ssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss...

output:

1 61041 38733 99773

result:

ok 4 number(s): "1 61041 38733 99773"

Test #43:

score: 0
Accepted
time: 29ms
memory: 35852kb

input:

zqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzq...

output:

22229 2 1 99772

result:

ok 4 number(s): "22229 2 1 99772"

Test #44:

score: 0
Accepted
time: 24ms
memory: 35128kb

input:

babababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababa...

output:

22229 2 1 99772

result:

ok 4 number(s): "22229 2 1 99772"

Test #45:

score: 0
Accepted
time: 20ms
memory: 35756kb

input:

llllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll...

output:

85548 90750 0 90749

result:

ok 4 number(s): "85548 90750 0 90749"

Test #46:

score: 0
Accepted
time: 18ms
memory: 34948kb

input:

bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbobbobbbbbobbbobbbbbbbbbbbbbbbbbbobbbbbbbbbbbbbbobbbbbbbbbbbobbbbbbbboobbobbbbbbbbbbobbbbbbbbbbbbbbbobbbbobbbbbbbbbbbbobbbbbbbbbbbbbbbbbbbbobbbbbbbbbbbbbobbbbbbbbbbbbbbbbboobbbbbobbbbbbbbbbbbbbbbbobbbbbbbbbbbbbbbbbbbbbbbbobbbobobbobbbbbbbbbbbbbbbbbbobbbbbbbobbbbbb...

output:

0 90750 0 90749

result:

ok 4 number(s): "0 90750 0 90749"

Test #47:

score: 0
Accepted
time: 11ms
memory: 27356kb

input:

llrlrrlrlrrllrrrrrlrlrlllllrrrrllrllrrllllrrlrlrllllllrrrlrllllllrrrlrrrrlrlrllrrrrrrrrlrlrrrlrrlrlllllrllrllrlrlllrrrrllllllllllrrrllrrlllrlrllrrrlllrrllrrrlllrlrlrlrlrlrllrlrrrrrrlrlrrllrrrrrrllrllrrlrlrlllrrrlrrrlrrrrrrrrrlrlllrlrlrlrlrllllrlrrrrrlllrlllrlrrlrrrlrlrllrrrrlllllllrllrlrlllllrrrrrrr...

output:

0 90750 0 90749

result:

ok 4 number(s): "0 90750 0 90749"

Test #48:

score: 0
Accepted
time: 10ms
memory: 31680kb

input:

llllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll...

output:

1 71220 19530 90749

result:

ok 4 number(s): "1 71220 19530 90749"

Test #49:

score: 0
Accepted
time: 11ms
memory: 34652kb

input:

qoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqo...

output:

42774 45375 0 90748

result:

ok 4 number(s): "42774 45375 0 90748"

Test #50:

score: 0
Accepted
time: 15ms
memory: 33236kb

input:

xtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxt...

output:

40492 43093 2508 88692

result:

ok 4 number(s): "40492 43093 2508 88692"

Test #51:

score: 0
Accepted
time: 16ms
memory: 40016kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

97181 91251 0 91250

result:

ok 4 number(s): "97181 91251 0 91250"

Test #52:

score: -100
Wrong Answer
time: 15ms
memory: 33016kb

input:

vvvvvvvvvvvvvvvvvvmmvvvvvvvvvvvvvmvvvvvvvvvvvvvvvvvvvvvvmvvvvvvvmvvvvvvvvvvvvvvvvvvvvvvvvvvvvvmvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvmvvvvvvvvvmvvvvvvvmvvvvvvmvvmvmvmvmvvvvvvvvvvvvvvvvvvvvvvvvvvvmvvvvvvvvvvvvvvvvvvvvvmvvvvvvvvvvvvvvvvvmvmvvvvvvvvvvmmvvvvvvvvvvvvvvvmvvmvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv...

output:

98 98 22809 22906

result:

wrong answer 1st numbers differ - expected: '6028', found: '98'