QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#537471 | #5256. Insertions | RockyYue | WA | 28ms | 39144kb | C++14 | 7.9kb | 2024-08-30 14:08:00 | 2024-08-30 14:08:00 |
Judging History
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)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: 24224kb
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: 29436kb
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: 22192kb
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: 29304kb
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: 24304kb
input:
gpgggpppg pg gpgg
output:
2 1 4 4
result:
ok 4 number(s): "2 1 4 4"
Test #6:
score: 0
Accepted
time: 3ms
memory: 31528kb
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: 22172kb
input:
aacaacacaa ca caca
output:
2 5 2 9
result:
ok 4 number(s): "2 5 2 9"
Test #8:
score: 0
Accepted
time: 7ms
memory: 31528kb
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: 24316kb
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: 31496kb
input:
b xbb b
output:
3 2 0 1
result:
ok 4 number(s): "3 2 0 1"
Test #11:
score: 0
Accepted
time: 2ms
memory: 22240kb
input:
nddnnndndn dnd ndndn
output:
3 1 5 5
result:
ok 4 number(s): "3 1 5 5"
Test #12:
score: 0
Accepted
time: 3ms
memory: 31480kb
input:
imiimmmm miimi i
output:
6 9 0 8
result:
ok 4 number(s): "6 9 0 8"
Test #13:
score: 0
Accepted
time: 3ms
memory: 22672kb
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: 27216kb
input:
m mmwmwmw wwmww
output:
0 2 0 1
result:
ok 4 number(s): "0 2 0 1"
Test #15:
score: 0
Accepted
time: 2ms
memory: 20148kb
input:
jmmmmjmmj jmjjjmjm mjmmmmjj
output:
0 10 0 9
result:
ok 4 number(s): "0 10 0 9"
Test #16:
score: 0
Accepted
time: 2ms
memory: 29228kb
input:
f ffffwff wffw
output:
0 2 0 1
result:
ok 4 number(s): "0 2 0 1"
Test #17:
score: 0
Accepted
time: 3ms
memory: 22192kb
input:
plpll llplll pppppppl
output:
0 6 0 5
result:
ok 4 number(s): "0 6 0 5"
Test #18:
score: 0
Accepted
time: 2ms
memory: 29308kb
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: 22172kb
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: 29756kb
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: 22648kb
input:
yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy...
output:
631 1000 0 999
result:
ok 4 number(s): "631 1000 0 999"
Test #22:
score: 0
Accepted
time: 0ms
memory: 22620kb
input:
annnnnnnnnnnnnnnnnnnnannnnnannannnnnnnnnannnnnnnnnnnnnnnnnnnnnnnnnnnnnnnannnnnnnnannnnnnnnnnnnnnnnnnnnnnnnnnannnannnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnannnnnnnnnnnnnnnnnnnnnnaannnnnnannnnnnnnnnnnnnnnnnnannnnnnnnnnnnnnnnnnnnnannnannnnnnnnnannannnnnnnnannnnnnnannannnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnan...
output:
0 1000 0 999
result:
ok 4 number(s): "0 1000 0 999"
Test #23:
score: 0
Accepted
time: 0ms
memory: 22916kb
input:
atatatataaaaaattattaaataataaaatttattattaaaataaattaaatattaaaataaaattatataatttaatattttattaatatattattatttaaattttaaaaattaaattttttaatttaattatttaaaataatttttattaaatttatttatattataaatttattataaatatttatatattttttatattatattatttaatttttttaaaatttaattttatttattttattatatataatttaaaataatttttttaaaaatattattttatttaaaatatat...
output:
0 1000 0 999
result:
ok 4 number(s): "0 1000 0 999"
Test #24:
score: 0
Accepted
time: 0ms
memory: 24316kb
input:
wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww...
output:
1 413 587 999
result:
ok 4 number(s): "1 413 587 999"
Test #25:
score: 0
Accepted
time: 0ms
memory: 22348kb
input:
rlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrl...
output:
315 2 1 998
result:
ok 4 number(s): "315 2 1 998"
Test #26:
score: 0
Accepted
time: 4ms
memory: 22280kb
input:
huhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuuuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhu...
output:
260 1 113 113
result:
ok 4 number(s): "260 1 113 113"
Test #27:
score: 0
Accepted
time: 0ms
memory: 24408kb
input:
pppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp...
output:
748 907 0 906
result:
ok 4 number(s): "748 907 0 906"
Test #28:
score: 0
Accepted
time: 0ms
memory: 24404kb
input:
kkkkkkkkkkkkkkkkkkkkkkkkpkkkkkkkkkpkppkkkkkkpkkkkkkkkkkkkkkkpkkkkkkkkkkkppkkpkkkkkkkkkkkpkkpkpkkpkkkkkpkkkkkkkkkkkkkkkkkkkkkkkkpkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkpkkkkkpkkkkkkkkkkkkkkkkkkkkkkkpkkkkkkkkkkkkkkkpkpkkkkkkkpkkkkkkkkkkkkkkkkkkkkkpkkkkkkkkkkkkkkpkkkkkkpkkkkkkkkkkkkkkkkkkkpkkkpkkkkkpkkkkkkkpkpk...
output:
0 907 0 906
result:
ok 4 number(s): "0 907 0 906"
Test #29:
score: 0
Accepted
time: 0ms
memory: 22228kb
input:
illillliiiiiilliiilliiilliliilililiililiiililililliliililiillilliliiiiiliiillllllllilliiilililiililililliiiliiililiillillliliiiliiliiliililllliiliiililiilllilllllliiliiiillilillllllillllililililliiiiliilliililllllilliliiiiilililiiiillliiillliililllilliiiiiilliilllllllliillllliiiiiiilliiliilllliiliil...
output:
0 907 0 906
result:
ok 4 number(s): "0 907 0 906"
Test #30:
score: 0
Accepted
time: 4ms
memory: 22348kb
input:
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii...
output:
1 702 0 701
result:
ok 4 number(s): "1 702 0 701"
Test #31:
score: 0
Accepted
time: 0ms
memory: 22264kb
input:
mymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymy...
output:
374 454 0 906
result:
ok 4 number(s): "374 454 0 906"
Test #32:
score: 0
Accepted
time: 3ms
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: 24340kb
input:
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii...
output:
937 966 0 965
result:
ok 4 number(s): "937 966 0 965"
Test #34:
score: 0
Accepted
time: 0ms
memory: 24292kb
input:
apaaaaaaaaaaaaaaaaaapaaaaaaaaaaaaaapapaaaaaapaaaaaaaapaaaaaaaaaaaaaaaaaaaaaaaaaaapaaaaaaaapaaaaaaaaaaaaaaaaapaaaaaaaaaaaaaaapaaaapapappaaaaaaaapaaappaaaapaapapaaaaaaapaaaappaaapaaaaaaaaaaaaaaaaaaaaaaaaaaaaaapaaaaaapaaaaaaaapaaaapppaapaaaaaaaaaaaapppaapaaaaaaaaaaaaaaaaaaaaaaapaaaaaaaaaaaaaaaaaaaaaaaa...
output:
35 64 600 663
result:
ok 4 number(s): "35 64 600 663"
Test #35:
score: 0
Accepted
time: 3ms
memory: 22544kb
input:
msmmssmmsmmmsmssmmmmmsmmmsmssssssssmmmmssmmsmmsmmmsmssmmmmsssmmsmmmssmssmsmmmsmssmsmmmsmmmsmssmsssmmssssmmmssmmssssmsmsmsmmmsmsmmsmsmssssssssmmmmmmsmmmsssmmmssssssssssmmmmssmsmsmmsmssssssssmmsmmsssmssmmmssssmsssmssmssmsmsmsmsmmsmmssmmsmmsmsmmssmmssmsmssmsssmsmsmsmmmmsmssmmmmsmmssmmmssssmsssssmmssmmm...
output:
0 966 0 965
result:
ok 4 number(s): "0 966 0 965"
Test #36:
score: 0
Accepted
time: 0ms
memory: 22248kb
input:
nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn...
output:
1 768 0 767
result:
ok 4 number(s): "1 768 0 767"
Test #37:
score: 0
Accepted
time: 0ms
memory: 24300kb
input:
jrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjr...
output:
468 483 0 964
result:
ok 4 number(s): "468 483 0 964"
Test #38:
score: 0
Accepted
time: 4ms
memory: 24596kb
input:
dkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkkkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdk...
output:
429 443 80 964
result:
ok 4 number(s): "429 443 80 964"
Test #39:
score: 0
Accepted
time: 28ms
memory: 38556kb
input:
tttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttt...
output:
44459 99774 0 99773
result:
ok 4 number(s): "44459 99774 0 99773"
Test #40:
score: 0
Accepted
time: 25ms
memory: 37504kb
input:
annnannnnnnnnnnnnnnnnnnnannnnnnnnnnannnnnnnnnnnnnnannananannnnnnnnnnnnnnnnannnnnnnnnnnnnnnnnannnnnnnnnnnnnnnnnnnnnnnnnnnnnnnannnnannnnnnnnnnnnnnnannnnnnnnnnnnnnnnnnnnannnnnnnnnnnnnnnnannnnnnnnnnnnnnnnnnnnannnnnnnaannnnnnnnnnnnnnnnnnnnnannannnnnnnnnnnnannnannnnnnnnannnnnnnnnnnnnnnnnnnnnannnannnaannan...
output:
0 99774 0 99773
result:
ok 4 number(s): "0 99774 0 99773"
Test #41:
score: 0
Accepted
time: 14ms
memory: 26644kb
input:
eyyeeeyyeyyeyeyyeyeeyyyyeeeeeyyyyeeeeyyyyyyyyyyyeeeeeeeeyeyyyeyyeeyyyeeyeeeeyeeyeeeeeeyyyeeyeeyeeeyyeyeyyeyyeyeyyyeyyeeeeeyeyyyyyeyyeyeyeeyyyyyeeyeyeeeyeeeyyyeeyeeyyyeeyyyeeyeyyeeeeyeyeeeyyeeyyeyeyyeeyyeyyyyeeeyyyeyyyeyyeeyeeeeeeyyyeyeyeyeeeeeyeyeyeyyeyeyyyyyyeyeeyeyyyeeeyeeyyeeyyyeyeyeyeyyyyyyeeeey...
output:
0 99774 0 99773
result:
ok 4 number(s): "0 99774 0 99773"
Test #42:
score: 0
Accepted
time: 21ms
memory: 32932kb
input:
ssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss...
output:
1 61041 38733 99773
result:
ok 4 number(s): "1 61041 38733 99773"
Test #43:
score: 0
Accepted
time: 21ms
memory: 35136kb
input:
zqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzq...
output:
22229 2 1 99772
result:
ok 4 number(s): "22229 2 1 99772"
Test #44:
score: 0
Accepted
time: 27ms
memory: 34960kb
input:
babababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababa...
output:
22229 2 1 99772
result:
ok 4 number(s): "22229 2 1 99772"
Test #45:
score: 0
Accepted
time: 15ms
memory: 36872kb
input:
llllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll...
output:
85548 90750 0 90749
result:
ok 4 number(s): "85548 90750 0 90749"
Test #46:
score: 0
Accepted
time: 20ms
memory: 34708kb
input:
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbobbobbbbbobbbobbbbbbbbbbbbbbbbbbobbbbbbbbbbbbbbobbbbbbbbbbbobbbbbbbboobbobbbbbbbbbbobbbbbbbbbbbbbbbobbbbobbbbbbbbbbbbobbbbbbbbbbbbbbbbbbbbobbbbbbbbbbbbbobbbbbbbbbbbbbbbbboobbbbbobbbbbbbbbbbbbbbbbobbbbbbbbbbbbbbbbbbbbbbbbobbbobobbobbbbbbbbbbbbbbbbbbobbbbbbbobbbbbb...
output:
0 90750 0 90749
result:
ok 4 number(s): "0 90750 0 90749"
Test #47:
score: 0
Accepted
time: 14ms
memory: 28264kb
input:
llrlrrlrlrrllrrrrrlrlrlllllrrrrllrllrrllllrrlrlrllllllrrrlrllllllrrrlrrrrlrlrllrrrrrrrrlrlrrrlrrlrlllllrllrllrlrlllrrrrllllllllllrrrllrrlllrlrllrrrlllrrllrrrlllrlrlrlrlrlrllrlrrrrrrlrlrrllrrrrrrllrllrrlrlrlllrrrlrrrlrrrrrrrrrlrlllrlrlrlrlrllllrlrrrrrlllrlllrlrrlrrrlrlrllrrrrlllllllrllrlrlllllrrrrrrr...
output:
0 90750 0 90749
result:
ok 4 number(s): "0 90750 0 90749"
Test #48:
score: 0
Accepted
time: 6ms
memory: 31932kb
input:
llllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll...
output:
1 71220 19530 90749
result:
ok 4 number(s): "1 71220 19530 90749"
Test #49:
score: 0
Accepted
time: 17ms
memory: 33700kb
input:
qoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqo...
output:
42774 45375 0 90748
result:
ok 4 number(s): "42774 45375 0 90748"
Test #50:
score: 0
Accepted
time: 14ms
memory: 34008kb
input:
xtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxt...
output:
40492 43093 2508 88692
result:
ok 4 number(s): "40492 43093 2508 88692"
Test #51:
score: 0
Accepted
time: 22ms
memory: 39144kb
input:
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
97181 91251 0 91250
result:
ok 4 number(s): "97181 91251 0 91250"
Test #52:
score: -100
Wrong Answer
time: 11ms
memory: 34556kb
input:
vvvvvvvvvvvvvvvvvvmmvvvvvvvvvvvvvmvvvvvvvvvvvvvvvvvvvvvvmvvvvvvvmvvvvvvvvvvvvvvvvvvvvvvvvvvvvvmvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvmvvvvvvvvvmvvvvvvvmvvvvvvmvvmvmvmvmvvvvvvvvvvvvvvvvvvvvvvvvvvvmvvvvvvvvvvvvvvvvvvvvvmvvvvvvvvvvvvvvvvvmvmvvvvvvvvvvmmvvvvvvvvvvvvvvvmvvmvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv...
output:
98 98 22809 22906
result:
wrong answer 1st numbers differ - expected: '6028', found: '98'