QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#706425#9464. 基础 01? 练习题TheZone100 ✓756ms89336kbC++209.4kb2024-11-03 11:15:252024-11-03 11:15:25

Judging History

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

  • [2024-11-03 11:15:25]
  • 评测
  • 测评结果：100
  • 用时：756ms
  • 内存：89336kb
查看
  • [2024-11-03 11:15:25]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include"debug.h"
#else
#define debug(...) void()
#endif
#define all(x) (x).begin(),(x).end()
template<class T>
auto ary(T *a,int l,int r){
	return vector<T>{a+l,a+1+r};
}
using ll=long long;
using ull=unsigned long long;
const int N=5e4+10,M=2e5+10,K=__lg(N)+2,mod=998244353;
int n,m,cnt[N],pw[N];
int f[K][N][2],g[K][N][2];
char a[N];
struct ques{
	int l,r;
}q[M];
struct val_t{
	int sum,ans,pw,val;
	val_t()=default;
	val_t(int a,int b,int c,int d):sum(a),ans(b),pw(c),val(d){}
};
val_t operator + (const val_t &a,const val_t &b){
	return val_t(
		(1ll*a.sum*b.pw+b.sum)%mod,(1ll*a.ans*b.pw+b.ans)%mod,
		1ll*a.pw*b.pw%mod,(1ll*a.val*b.pw+b.val)%mod
	);
}
struct laz_t{
	int laz,pw,sum,val;
	laz_t():laz(0),pw(1),sum(0),val(0){};
	laz_t(int a,int b,int c,int d):laz(a),pw(b),sum(c),val(d){}
	operator bool()const{
		return laz||pw!=1||sum||val;
	}
};
val_t& operator += (val_t &a,const laz_t &b){
	a.ans=(1ll*a.ans*b.pw+1ll*a.sum*b.sum+1ll*a.val*b.val)%mod;
	a.sum=(a.sum+1ll*a.val*b.laz)%mod;
	return a;
}
laz_t& operator += (laz_t &a,const laz_t &b){
	a.pw=1ll*a.pw*b.pw%mod;
	a.sum=(1ll*a.sum*b.pw+b.sum)%mod;
	a.val=(1ll*a.val*b.pw+1ll*a.laz*b.sum+b.val)%mod;
	a.laz=(a.laz+b.laz)%mod;
	return a;
}
int lim;
val_t t[N<<2];
laz_t laz[N<<2];
#define pushup(rt) \
	(t[rt].sum=(1ll*t[rt<<1].sum*t[rt<<1|1].pw+t[rt<<1|1].sum)%mod,\
	t[rt].ans=(1ll*t[rt<<1].ans*t[rt<<1|1].pw+t[rt<<1|1].ans)%mod)
#define pushlaz(rt,x) (t[rt]+=x,laz[rt]+=x)
#define pushdown(rt) \
	laz[rt]&&(pushlaz(rt<<1,laz[rt]),\
	pushlaz(rt<<1|1,laz[rt]),\
	laz[rt]=laz_t(),0)
void build(){
	for(lim=1;lim<=n+1;lim<<=1);
	for(int i=1;i<=n;i++)t[lim+i]=val_t(0,0,1+(a[i]=='?'),1);
	for(int i=lim;i>=1;i--)t[i]=t[i<<1]+t[i<<1|1];
}
void push(int l,int r){
	static int stk[99],top;
	for(top=0,l+=lim-1,r+=lim+1;l^r^1;){
		stk[++top]=l>>=1,stk[++top]=r>>=1;
	}
	for(;l>>=1;)stk[++top]=l;
	for(int i=top;i>=1;i--)pushdown(stk[i]);
}
void update(int l,int r,const laz_t &x){
	push(l,r);
	for(l+=lim-1,r+=lim+1;l^r^1;){
		~l&1&&(pushlaz(l^1,x),0);
		r&1&&(pushlaz(r^1,x),0);
		l>>=1,r>>=1,pushup(l),pushup(r);
	}
	for(;l>>=1;)pushup(l);
}
val_t query(int l,int r){
	push(l,r);
	val_t a=val_t(0,0,1,0),b=a;
	for(l+=lim-1,r+=lim+1;l^r^1;l>>=1,r>>=1){
		~l&1&&(a=a+t[l^1],0);
		r&1&&(b=t[r^1]+b,0);
	}
	return a+b;
}
vector<int>o[N];
vector<tuple<int,int,int>>p[N];
int ans[M];
void insert(int l,int r,int x,int y,int w){
	if(l>r||x>y)return;
	p[r].push_back({x,y,w});
	p[l-1].push_back({x,y,-w});
}
struct IO{
    static const int S=1<<21;
    char buf[S],*p1,*p2;int st[105],Top;
    ~IO(){clear();}
    inline void clear(){fwrite(buf,1,Top,stdout);Top=0;}
    inline void pc(const char c){Top==S&&(clear(),0);buf[Top++]=c;}
    inline char gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
    inline IO&operator >> (char&x){while(x=gc(),x==' '||x=='\n'||x=='\r');return *this;}
    template<typename T>inline IO&operator >> (T&x){
        x=0;bool f=0;char ch=gc();
        while(ch<'0'||ch>'9'){if(ch=='-') f^=1;ch=gc();}
        while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=gc();
        f?x=-x:0;return *this;
    }
    inline IO&operator << (const char c){pc(c);return *this;}
    template<typename T>inline IO&operator << (T x){
        if(x<0) pc('-'),x=-x;
        do{st[++st[0]]=x%10,x/=10;}while(x);
        while(st[0]) pc('0'+st[st[0]--]);return *this;
    }
}fin,fout;
int main(){
	fin>>n>>m;
	for(int i=1;i<=n;i++)fin>>a[i];
	for(int i=n;i>=1;i--)cnt[i]=cnt[i+1]+(a[i]=='?');
	for(int i=pw[0]=1;i<=n;i++)pw[i]=pw[i-1]*2%mod;
	for(int i=1;i<=m;i++){
		fin>>q[i].l>>q[i].r,++q[i].l,++q[i].r;
		o[q[i].l].push_back(i);
	}
	for(int i=1;i<=n;i++)for(int c:{0,1}){
		f[0][i][c]=g[0][i][c]=a[i]!='0'+!c;
	}
	for(int i=0;(1<<i)<=n;i++){
		for(int j=1;j<=n;j++){
			for(int c:{0,1}){
				f[i+1][j][c]=f[i][j][c]==(1<<i)?f[i][j+(1<<i)][!c]+(1<<i):f[i][j][c];
				g[i+1][j][c]=g[i][j][c]==(1<<i)?g[i][j-(1<<i)][!c]+(1<<i):g[i][j][c];
			}
		}
	}
	for(int i=1,k=__lg(n)+1;i<n;i++){
		for(int x:{0,1})for(int y:{0,1}){
			insert(i-g[k][i][x]+1,i,i+1,i+f[k][i+1][y],1);
		}
	}
	for(int k=0;(1<<k)<=n;k++){
		for(int i=1,j=1+(1<<k);j<n;i++,j++){
			for(int x:{0,1})if(f[k][i+1][x]==(1<<k)){
				int y=k&1^x;
				insert(i-g[k][i][!y]+1,i,j+1,j+f[k][j+1][!x],-1);
			}
		}
	}
	for(int i=1;i<=n;i++)insert(i,i,i,i,1+(a[i]=='?'));
	build();
	for(int i=n;i>=1;i--){
		sort(all(p[i]));
		for(int l=0,r;l<p[i].size();l=r){
			auto [st,ed,sum]=p[i][l];
			for(r=l+1;r<p[i].size()&&st==get<0>(p[i][r])&&ed==get<1>(p[i][r]);r++)sum+=get<2>(p[i][r]);
			update(st,ed,laz_t(sum,1,0,0));
		}
		update(1,n,laz_t(0,1+(a[i]=='?'),1,0));
		for(int id:o[i])ans[id]=query(q[id].l,q[id].r).ans;
	}
	for(int i=1;i<=m;i++)(ans[i]+=mod)%=mod;
	for(int i=1;i<=m;i++)fout<<ans[i]<<'\n';
	return 0;
}
#ifdef DEBUG
#include"debug.hpp"
#endif
/*#include<bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include"debug.h"
#else
#define debug(...) void()
#endif
#define all(x) (x).begin(),(x).end()
template<class T>
auto ary(T *a,int l,int r){
	return vector<T>{a+l,a+1+r};
}
using ll=long long;
using ull=unsigned long long;
const int N=5e4+10,M=2e5+10,K=__lg(N)+2,mod=998244353;
int n,m,cnt[N],pw[N];
int f[K][N][2],g[K][N][2];
char a[N];
struct ques{
	int l,r;
}q[M];
struct val_t{
	int sum,ans,pw,val;
	val_t()=default;
	val_t(int a,int b,int c,int d):sum(a),ans(b),pw(c),val(d){}
};
val_t operator + (const val_t &a,const val_t &b){
	return val_t(
		(1ll*a.sum*b.pw+b.sum)%mod,(1ll*a.ans*b.pw+b.ans)%mod,
		1ll*a.pw*b.pw%mod,(1ll*a.val*b.pw+b.val)%mod
	);
}
struct laz_t{
	int laz,pw,sum,val;
	laz_t():laz(0),pw(1),sum(0),val(0){};
	laz_t(int a,int b,int c,int d):laz(a),pw(b),sum(c),val(d){}
	operator bool()const{
		return laz||pw!=1||sum||val;
	}
};
val_t& operator += (val_t &a,const laz_t &b){
	a.ans=(1ll*a.ans*b.pw+1ll*a.sum*b.sum+1ll*a.val*b.val)%mod;
	a.sum=(a.sum+1ll*a.val*b.laz)%mod;
	return a;
}
laz_t& operator += (laz_t &a,const laz_t &b){
	a.pw=1ll*a.pw*b.pw%mod;
	a.sum=(1ll*a.sum*b.pw+b.sum)%mod;
	a.val=(1ll*a.val*b.pw+1ll*a.laz*b.sum+b.val)%mod;
	a.laz=(a.laz+b.laz)%mod;
	return a;
}
int lim;
val_t t[N<<2];
laz_t laz[N<<2];
#define pushup(rt) \
	(t[rt].sum=(1ll*t[rt<<1].sum*t[rt<<1|1].pw+t[rt<<1|1].sum)%mod,\
	t[rt].ans=(1ll*t[rt<<1].ans*t[rt<<1|1].pw+t[rt<<1|1].ans)%mod)
#define pushlaz(rt,x) (t[rt]+=x,laz[rt]+=x)
#define pushdown(rt) \
	laz[rt]&&(pushlaz(rt<<1,laz[rt]),\
	pushlaz(rt<<1|1,laz[rt]),\
	laz[rt]=laz_t(),0)
void build(){
	for(lim=1;lim<=n+1;lim<<=1);
	for(int i=1;i<=n;i++)t[lim+i]=val_t(0,0,1+(a[i]=='?'),1);
	for(int i=lim;i>=1;i--)t[i]=t[i<<1]+t[i<<1|1];
}
void push(int l,int r){
	static int stk[99],top;
	for(top=0,l+=lim-1,r+=lim+1;l^r^1;){
		stk[++top]=l>>=1,stk[++top]=r>>=1;
	}
	for(;l>>=1;)stk[++top]=l;
	for(int i=top;i>=1;i--)pushdown(stk[i]);
}
void update(int l,int r,const laz_t &x){
	push(l,r);
	for(l+=lim-1,r+=lim+1;l^r^1;){
		~l&1&&(pushlaz(l^1,x),0);
		r&1&&(pushlaz(r^1,x),0);
		l>>=1,r>>=1,pushup(l),pushup(r);
	}
	for(;l>>=1;)pushup(l);
}
val_t query(int l,int r){
	push(l,r);
	val_t a=val_t(0,0,1,0),b=a;
	for(l+=lim-1,r+=lim+1;l^r^1;l>>=1,r>>=1){
		~l&1&&(a=a+t[l^1],0);
		r&1&&(b=t[r^1]+b,0);
	}
	return a+b;
}
vector<int>o[N];
vector<tuple<int,int,int>>p[N];
int ans[M];
void insert(int l,int r,int x,int y,int w){
	if(l>r||x>y)return;
	p[r].push_back({x,y,w});
	p[l-1].push_back({x,y,-w});
}
struct IO{
    static const int S=1<<21;
    char buf[S],*p1,*p2;int st[105],Top;
    ~IO(){clear();}
    inline void clear(){fwrite(buf,1,Top,stdout);Top=0;}
    inline void pc(const char c){Top==S&&(clear(),0);buf[Top++]=c;}
    inline char gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
    inline IO&operator >> (char&x){while(x=gc(),x==' '||x=='\n'||x=='\r');return *this;}
    template<typename T>inline IO&operator >> (T&x){
        x=0;bool f=0;char ch=gc();
        while(ch<'0'||ch>'9'){if(ch=='-') f^=1;ch=gc();}
        while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=gc();
        f?x=-x:0;return *this;
    }
    inline IO&operator << (const char c){pc(c);return *this;}
    template<typename T>inline IO&operator << (T x){
        if(x<0) pc('-'),x=-x;
        do{st[++st[0]]=x%10,x/=10;}while(x);
        while(st[0]) pc('0'+st[st[0]--]);return *this;
    }
}fin,fout;
int main(){
	fin>>n>>m;
	for(int i=1;i<=n;i++)fin>>a[i];
	for(int i=n;i>=1;i--)cnt[i]=cnt[i+1]+(a[i]=='?');
	for(int i=pw[0]=1;i<=n;i++)pw[i]=pw[i-1]*2%mod;
	for(int i=1;i<=m;i++){
		fin>>q[i].l>>q[i].r,++q[i].l,++q[i].r;
		o[q[i].l].push_back(i);
	}
	for(int i=1;i<=n;i++)for(int c:{0,1}){
		f[0][i][c]=g[0][i][c]=a[i]!='0'+!c;
	}
	for(int i=0;(1<<i)<=n;i++){
		for(int j=1;j<=n;j++){
			for(int c:{0,1}){
				f[i+1][j][c]=f[i][j][c]==(1<<i)?f[i][j+(1<<i)][!c]+(1<<i):f[i][j][c];
				g[i+1][j][c]=g[i][j][c]==(1<<i)?g[i][j-(1<<i)][!c]+(1<<i):g[i][j][c];
			}
		}
	}
	for(int i=1,k=__lg(n)+1;i<n;i++){
		for(int x:{0,1})for(int y:{0,1}){
			insert(i-g[k][i][x]+1,i,i+1,i+f[k][i+1][y],1);
		}
	}
	for(int k=0;(1<<k)<=n;k++){
		for(int i=1,j=1+(1<<k);j<n;i++,j++){
			for(int x:{0,1})if(f[k][i+1][x]==(1<<k)){
				int y=k&1^x;
		for(int id:o[i])ans[id]=query(q[id].l,q[id].r).ans;
	}
	for(int i=1;i<=m;i++)(ans[i]+=mod)%=mod;
	for(int i=1;i<=m;i++)fout<<ans[i]<<'\n';
	return 0;
}
#ifdef DEBUG
#include"debug.hpp"
#endif*/
源文件, 语言: C++20

详细

Subtask #1:

score: 10
Accepted

Test #1:

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

input:

15 15
0???0??01???1??
2 14
0 9
6 10
1 14
1 14
0 12
5 14
6 7
0 6
4 14
1 12
10 10
0 14
1 12
4 7

output:

25883
2344
112
56425
56425
12963
4531
6
666
5212
11875
2
60786
11875
37

result:

ok 15 numbers

Test #2:

score: 10
Accepted
time: 2ms
memory: 20088kb

input:

15 15
011?1?0101??110
0 11
2 10
0 13
2 12
3 5
2 12
3 5
12 13
1 14
1 5
8 13
9 12
2 10
0 11
7 8

output:

803
285
952
732
23
732
23
3
940
48
69
37
285
803
3

result:

ok 15 numbers

Test #3:

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

input:

15 15
100110?1010?01?
9 9
6 11
1 4
0 13
7 7
9 13
3 14
0 0
0 13
0 12
0 10
6 11
4 8
3 13
0 13

output:

1
77
10
265
1
25
384
1
265
251
109
77
30
175
265

result:

ok 15 numbers

Test #4:

score: 10
Accepted
time: 2ms
memory: 22112kb

input:

15 15
??????0?0??????
8 10
0 14
9 12
2 13
1 6
7 12
0 13
6 14
0 11
0 14
4 14
5 14
0 8
4 5
1 13

output:

23
439848
146
41764
540
540
202272
3703
41802
439848
18776
8386
3703
12
92312

result:

ok 15 numbers

Test #5:

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

input:

15 15
?1??0?0??010?1?
3 14
4 5
0 14
0 13
4 8
12 13
1 5
5 8
11 13
3 3
1 12
0 2
5 14
11 12
4 12

output:

3128
6
15531
6994
99
6
101
73
12
2
2842
23
1305
6
522

result:

ok 15 numbers

Test #6:

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

input:

15 15
10????1001?11?1
0 14
0 5
0 14
5 13
4 9
10 14
6 13
0 14
1 9
0 13
6 13
1 11
1 13
9 13
4 5

output:

4184
279
4184
276
78
46
109
4184
531
3878
109
1446
3516
46
12

result:

ok 15 numbers

Subtask #2:

score: 10
Accepted

Test #7:

score: 10
Accepted
time: 19ms
memory: 24660kb

input:

20 200000
???10?10???????1????
1 19
2 17
5 19
6 19
6 15
5 19
1 11
0 15
4 6
3 16
10 13
12 18
16 16
0 15
7 14
2 11
14 19
9 16
0 18
11 16
7 13
1 17
5 18
7 7
6 10
4 17
5 19
2 9
0 16
1 19
5 14
4 19
0 11
0 16
15 19
0 12
1 15
4 17
13 16
3 14
4 13
5 13
3 10
0 19
2 17
6 18
0 18
7 10
3 18
10 14
1 13
0 16
0 19...

output:

1336712
138392
234942
106457
4426
234942
5914
141418
12
28991
146
1346
2
141418
3235
2622
540
3235
1346550
540
1346
298458
108555
1
107
55692
234942
504
300854
1336712
9100
258457
13090
300854
206
28541
65634
55692
73
12242
4720
3994
479
2835916
138392
48773
1346550
73
133840
412
28291
300854
283591...

result:

ok 200000 numbers

Test #8:

score: 10
Accepted
time: 19ms
memory: 24392kb

input:

20 200000
?10???1101001101??11
2 17
8 16
0 15
1 17
11 13
1 6
2 13
5 19
2 4
1 8
1 6
0 2
4 8
2 5
0 13
1 14
11 15
16 18
14 15
4 19
0 17
9 19
8 13
0 3
0 7
8 19
4 19
17 17
12 15
2 8
0 19
4 19
1 19
13 17
0 10
0 19
19 19
4 11
0 19
0 19
0 16
1 16
6 6
1 14
12 14
7 13
1 2
2 16
2 5
3 18
0 16
6 16
4 8
12 17
8 9...

output:

2760
82
1396
2948
6
141
463
636
23
209
141
12
51
73
1115
593
15
23
3
1380
6288
198
21
40
427
226
1380
2
10
168
6960
1380
3284
56
702
6960
1
123
6960
6960
2984
1394
1
593
6
28
3
1300
73
2780
2984
116
51
75
3
136
636
2944
226
1380
1300
6288
6960
141
602
175
35
23
2932
38
1396
3
29
12
294
593
6656
184
...

result:

ok 200000 numbers

Test #9:

score: 10
Accepted
time: 18ms
memory: 20032kb

input:

20 200000
01101010101?001?011?
2 8
8 19
2 16
11 17
0 16
7 19
3 11
0 14
16 18
4 9
6 19
4 17
6 12
7 10
2 19
6 17
0 12
1 19
0 19
3 8
0 18
2 14
1 19
10 14
2 19
9 19
2 15
13 14
3 15
9 13
12 19
12 14
1 12
6 6
13 15
0 15
10 18
0 19
0 19
8 17
0 18
0 13
7 11
4 5
1 19
1 18
1 17
7 12
0 16
1 19
1 10
10 18
1 2
3...

output:

22
406
247
96
291
460
61
122
6
18
492
242
48
10
620
210
102
660
708
18
338
100
660
26
620
352
224
3
208
27
116
6
90
1
12
268
136
708
708
167
338
111
29
3
660
314
294
40
291
660
35
136
3
18
230
167
708
18
352
1
18
21
141
25
226
12
20
72
12
708
26
1
210
10
99
50
274
29
708
274
33
50
588
73
167
192
708...

result:

ok 200000 numbers

Test #10:

score: 10
Accepted
time: 20ms
memory: 22208kb

input:

20 200000
????????0?????0?????
0 19
1 19
4 17
9 12
3 12
0 18
1 12
6 7
1 9
8 11
4 19
1 5
0 19
19 19
5 15
1 9
0 5
2 18
12 17
3 7
2 2
0 18
8 18
10 15
8 13
15 16
9 14
2 19
9 17
12 16
3 6
0 9
2 9
1 15
4 18
9 18
5 8
2 8
4 13
2 16
12 17
0 16
5 16
9 19
1 19
3 11
13 18
2 16
1 15
6 19
0 10
6 12
1 4
14 17
2 19...

output:

20336544
9597862
210735
146
17346
9597284
87146
12
7568
73
985734
412
20336544
2
19633
7568
1080
2114106
540
412
2
9597284
19606
540
540
12
540
4513692
7568
206
146
17346
3235
456646
457188
17346
73
1346
17346
456984
540
2113112
43751
39128
9597862
7568
540
456984
456646
210668
39128
1346
146
73
451...

result:

ok 200000 numbers

Test #11:

score: 10
Accepted
time: 23ms
memory: 24612kb

input:

20 200000
??10?1011?01????????
11 13
0 1
0 19
0 16
6 10
7 19
1 4
2 16
7 19
8 14
3 14
15 17
5 18
14 19
5 11
1 19
10 18
4 18
14 17
1 19
2 18
0 19
11 18
16 19
0 12
1 4
10 15
11 14
13 15
3 11
1 12
7 10
7 13
10 13
7 18
12 15
15 18
10 19
9 14
3 15
6 18
13 16
1 19
7 11
4 18
2 12
6 14
2 17
2 18
7 13
4 6
7 1...

output:

23
12
388332
41750
26
25671
40
8695
25671
378
1640
46
14667
1080
47
182132
3869
32150
146
182132
39318
388332
3235
146
1986
40
279
73
46
140
900
18
187
38
11717
146
146
8845
292
3576
13131
146
182132
27
32150
389
534
18527
39318
187
12
11717
86572
8695
900
140
12
2718
3101
35478
16608
388332
898
12
...

result:

ok 200000 numbers

Test #12:

score: 10
Accepted
time: 23ms
memory: 26576kb

input:

20 200000
?1??111??0?1??1?0100
17 19
12 15
9 10
0 18
15 19
3 11
2 19
0 2
4 13
4 13
1 15
0 19
0 19
5 8
5 9
4 16
0 19
5 8
2 9
17 17
10 15
3 13
2 16
5 17
0 18
11 19
0 17
3 18
12 16
0 19
13 17
6 18
5 9
0 16
0 2
2 9
4 18
2 17
0 19
4 18
0 3
5 12
0 19
0 8
7 16
4 7
0 17
14 18
0 13
0 17
5 18
4 10
1 12
0 18
1...

output:

6
73
6
37608
29
402
18272
23
1023
1023
13068
40576
40576
35
49
2995
40576
35
320
1
278
2206
13452
3263
37608
284
34104
7978
107
40576
57
3460
49
30936
23
320
3829
15036
40576
3829
73
405
40576
780
2365
15
34104
30
11672
34104
3701
144
2356
37608
2
380
106
2531
37608
2365
40576
15036
5
2
28248
13452
...

result:

ok 200000 numbers

Subtask #3:

score: 5
Accepted

Test #13:

score: 5
Accepted
time: 122ms
memory: 40252kb

input:

50000 200000
011001101001011?10011001011010010110011010011001011?011010010110?0011001011001101?011?010?10100101100110100110010110011?1001011010011001011?10010?1?0?10100101101?01100101100110100110010110?001011001101001100101100?10100101101?0110?10110011010011001011010010110011010010110100110?10110100...

output:

15
21
66
21
6
78
38
105
105
61
28
10
141
187
42
111
45
3
45
151
10
15
6
28
28
18
45
102
10
105
21
45
3
66
120
105
91
1
78
66
10
105
6
6
170
45
162
6
28
105
105
6
45
6
36
91
173
343
74
78
40
45
1
120
78
120
45
21
66
71
45
170
10
55
3
3
82
1
1
6
132
45
28
105
10
1
105
105
2
12
15
78
3
51
78
36
1
45
12...

result:

ok 200000 numbers

Test #14:

score: 5
Accepted
time: 673ms
memory: 77184kb

input:

50000 200000
???????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????...

output:

412
146
412
12
412
1080
1821748
2692
78256
78256
412
34692
6470
384184
174292
384184
46
12
839610
12
34692
1080
1080
15136
839610
12
34692
46
174292
2
2
2692
12
1821748
46
412
174292
34692
146
34692
46
1080
6470
839610
1080
174292
174292
15136
412
46
34692
2692
1080
15136
78256
78256
384184
384184
1...

result:

ok 200000 numbers

Test #15:

score: 5
Accepted
time: 140ms
memory: 40204kb

input:

50000 200000
1?0?0110100101100?10?001011?100110010110011?10?1?00101?01?010110011?1001011?10??1??10110100101?001101001100101?0?110100?0110100110?101?0011??0?11?010110100???10011?1001100?01100110?001011?100110010110??01011?011010010110100?10010?10?110????100101101001011???1010???1101?0110?1011010010?1...

output:

12
156
10
572
1040
3
71
53
50
284
3854
105
68
45
122
214
2047
413
266
45
10
126
1056
1
520
6
94
49
246
6
132
6
1
55
1
28
20
12
12
530
4491
1283
38
189
6
40
110
230
1773
193
233
1
3
574
1
52
21
37
583
3
89
38
771
3
229
36
23
662
620
301
36
15
301
73
2
443
38
18
246
113
42
950
21
53
28
833
202
196
30
...

result:

ok 200000 numbers

Test #16:

score: 5
Accepted
time: 126ms
memory: 39852kb

input:

50000 200000
?0100110010110011010010110100110010110100?01100110100?01101001100101100110100110010110100101100110100101101001100101101001011?0110100110010110011010010110100110010110100101100110100101101001100101100110100110010110100101100110100110010110011010010110100110010110011010011001011010010?100...

output:

36
66
120
6
28
6
55
3
66
138
36
105
36
3
3
10
55
20
45
66
91
66
36
55
66
78
91
10
78
6
66
55
15
328
110
6
105
1
21
55
105
1
91
1
10
1
36
36
6
1
36
45
6
6
78
184
55
15
105
45
36
1
55
10
28
28
36
66
36
45
120
120
15
28
66
21
78
28
21
66
127
45
10
3
66
105
10
36
1
1
28
10
229
36
3
1
120
1
3
28
91
21
6
...

result:

ok 200000 numbers

Test #17:

score: 5
Accepted
time: 176ms
memory: 44680kb

input:

50000 200000
?1?0?1??1???10??????1?010??0??1?1?0?1?0?011???1?10??1?1??1?1100???1?01?00?0???????00101?0???010011?01?11??00??110?11?100110?1?11???1001?0110?10?10??0101?0011???01100??110???0?0??011?1?110?00110?10110?1??1?????010?10?001?0??01?01?0??11??1??10?11?0101?001??????0110?00?1??1????011????110??...

output:

35
38
20
6
12542
73
145
89
107
2308
124
24655
3087
475
402
662
16105
140
844
7236
25117
2343
1085
3504
4424
10103
142
1380
6
530
194
46
2663
1002
3
4709
540
12839
1551
203
828
20
1802
145
621
7301
2810
715
1074
102
1659
12
6
112
3
6
14022
30
23
23
1006
891
1346
12
4262
123
126
8679
1346
481
2294
160...

result:

ok 200000 numbers

Test #18:

score: 5
Accepted
time: 129ms
memory: 39536kb

input:

50000 200000
1011010110100111011001?01001?110?0??1?0101?1100000010010?1?01001101101010011?0101100?1010010001?11?0110?00110011001100?100001010010110?00110010010?10?110?0101001?1011010?11010100101101000??0?1010010?1001101?010110100?10010110010011??0?1011010011?00?1?1010100110010011010?1?0010?101?0?011...

output:

36
10
107
6
6
36
47
81
54
12
25
28
38
34
67
1
125
64
248
18
1
236
128
55
231
132
240
17
11
45
49
266
33
460
145
15
15
142
23
94
45
6
40
1
10
12
18
389
215
10
74
10
164
28
1
71
210
6
83
69
14
36
2
60
27
43
244
51
58
66
115
128
1
10
23
1
47
78
1
6
12
3
88
29
3
1
1
66
10
71
10
26
43
124
3
15
80
168
20
...

result:

ok 200000 numbers

Subtask #4:

score: 5
Accepted

Test #19:

score: 5
Accepted
time: 76ms
memory: 35064kb

input:

50000 1
0101101001100101100110100110010110100101100110100110010110011010010110100110010110011010011001011010010110011010010110100110010110100101100110100110010110011010010110100110010110011010011001011010010110011010011001011001101001011010011001011010010110011010010110100110010110011010011001011010...

output:

132414834

result:

ok 1 number(s): "132414834"

Test #20:

score: 5
Accepted
time: 79ms
memory: 34148kb

input:

50000 1
1001011001101001100101101001011001101001011010011001011010010110011010011001011001101001011010011001011010010110011010010110100110010110011010011001011010010110011010011001011001101001011010011001011001101001100101101001011001101001011010011001011010010110011010011001011001101001011010011001...

output:

165181456

result:

ok 1 number(s): "165181456"

Test #21:

score: 5
Accepted
time: 69ms
memory: 34900kb

input:

50000 1
0010110011010011001011001101001011010011001011001101001100101101001011001101001011010011001011010010110011010011001011001101001011010011001011010010110011010010110100110010110011010011001011010010110011010010110100110010110100101100110100110010110011010010110100110010110011010011001011010010...

output:

384873

result:

ok 1 number(s): "384873"

Test #22:

score: 5
Accepted
time: 72ms
memory: 34912kb

input:

50000 1
1011001101001011010011001011010010110011010011001011001101001011010011001011001001011010011001011010010110011010011001011001101001011010011001011010010110011010010110100110010110011010011001011010010110011010011001011001101001011010011001011001101001100101101001011001101001011010011001011010...

output:

272208464

result:

ok 1 number(s): "272208464"

Test #23:

score: 5
Accepted
time: 81ms
memory: 34952kb

input:

50000 1
0110010110100101100110100110010110011010010110100110010110011010011001011010010110011010010110100110010110100101100110100101101001100101100110100110010110100101100110101101001100100110010110100101100110100101101001100101101001011001101001100101100110100101101001100101100110100110010110100101...

output:

6615896

result:

ok 1 number(s): "6615896"

Test #24:

score: 5
Accepted
time: 77ms
memory: 34764kb

input:

50000 1
1001011010010101001100010110100011000110100111101000101100110001100101100000111010110010101100101010001110011111001100101000101101101010011011101100101101001011000110011001010110110000110100101101010010110110011010100110011010101001100100100110110010110100110100100110011010001001100101100010...

output:

41003648

result:

ok 1 number(s): "41003648"

Subtask #5:

score: 15
Accepted

Test #25:

score: 15
Accepted
time: 75ms
memory: 35580kb

input:

50000 1
01011010011000110100110010110010?1001?0001011001101?001011001101?0101101?011011001101001010?10100101101001100101?01100101010?101001100110?1011010011001011010??110011?1?011001?1100110?101101001100101100100110010110011100110100101001?1?0?00?100101101001011001101001011100?1010010110101101001011...

output:

111365458

result:

ok 1 number(s): "111365458"

Test #26:

score: 15
Accepted
time: 143ms
memory: 42376kb

input:

50000 1
0??0?1?10?????101??1??10??0???01001?????1??0?1?1?0101?????1?00???1?01???001?001?????0????1?01???0?110???1?0??10?0????10?????0???1????01???0011??0?1??1??????0???11???1???0????101?0?00101??0?10?00????10????????0?101101??110???1?001??????1????11??0?10???0?10???1?1?0??0???0?011?100?0????110?00??...

output:

825836622

result:

ok 1 number(s): "825836622"

Test #27:

score: 15
Accepted
time: 84ms
memory: 35092kb

input:

50000 1
11001101001100101101001011?01101001?11010011001011?1001011001101001100?01100110100101101001100101101001011001101001011?100110010110011010011001011010010110011010010110100110010110100101100110100110010110011010010110100110010110011?1001??0101101001011001?01001100101100110100101101001100101101...

output:

624938164

result:

ok 1 number(s): "624938164"

Test #28:

score: 15
Accepted
time: 72ms
memory: 34524kb

input:

50000 1
1100101100110100101101001100101100110100110010110100101100110100101101001100101101001011001101001100101100110100101101001100101101001011001101001011010011001011001101001100101101001011001101001011010011001011010010110011010011001011001101001011010011001011001101001110100101101001100101101001...

output:

554863263

result:

ok 1 number(s): "554863263"

Test #29:

score: 15
Accepted
time: 96ms
memory: 36600kb

input:

50000 1
011001101?011001011010??0110?11010?1?0010110011010010110??01100101??01101001100101?010?1?1100?10100?0?1?10011?01??101001???00110?00?100??1?001?0100?011010?11?010?1010?101100110100??1?010011001011?0???1?0?1001011??0010110011010010110?0?110010???1001011?0110100?1?0?0110011011?010011?0??110?110...

output:

586569695

result:

ok 1 number(s): "586569695"

Test #30:

score: 15
Accepted
time: 632ms
memory: 71672kb

input:

50000 1
????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????...

output:

329743182

result:

ok 1 number(s): "329743182"

Subtask #6:

score: 5
Accepted

Test #31:

score: 5
Accepted
time: 5ms
memory: 28348kb

input:

500 1000
011000100010010010010010110010101100101100101011010010011001101001011010011000010011010001011010000001100101100110100101101001001011010010110010110100101100111001100111010011010010110100110010110100101100110101000101100110100110010110100101100110100101101?01101101100101011001010010100110010...

output:

399
1770
1496
922
2273
23256
14888
21468
5050
11956
7336
16724
1640
23288
23076
5699
23296
556
10300
23036
2274
14904
344
958
8912
1922
372
16048
14908
2830
20496
748
17988
22832
21300
22324
17996
23792
3
17104
19492
474
8664
14960
19820
339
1402
12048
24060
20344
19324
20304
5254
3962
20340
1532
52...

result:

ok 1000 numbers

Test #32:

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

input:

500 1000
0010100100010011011101100101000010010110100101101001010010110101001?1001?0100100010010100010110110010111101110110001010010001011001010001010001001100101010011010110100110101111001001010101101000101100101100111011110110100100011010?101110010101111000101010000001110011010011000101100100101100...

output:

137
2544
479
2586
2756
19644
43352
2768
2692
12260
7068
92416
810
28
17768
91888
15836
15220
2618
327
3972
139
1504
7832
1069
12668
2576
45752
8904
2500
2582
94864
10356
95856
3446
15260
492
17572
15
43144
116
2898
81456
1738
3482
1130
4416
216
473
16884
2130
17812
39408
46312
3
2184
2774
224
7792
6...

result:

ok 1000 numbers

Test #33:

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

input:

500 1000
101001001?11011010010111100110010110101010010001111?10101010001101011011001110100101110011010011101011101110110100101011000001000110110000101000010010011?0100100100010001010001010011010011010001?011010011001110110101101011110100011100100101110011011010110101101010110100001101001110000101101...

output:

11024
63280
293632
2683
21432
712
3282
26296
3014
51856
3280
319520
156
19816
150912
1655
4506
675776
1212
2286
17620
1130
1066
28424
2306
9816
8080
2014
128320
11132
658880
740
324
2986
316832
678848
2560
4204
65440
2118
1138
5146
26664
64880
188
7392
1
145808
20808
568
9720
8996
6648
70352
35
1175...

result:

ok 1000 numbers

Test #34:

score: 5
Accepted
time: 3ms
memory: 22160kb

input:

500 1000
11010011001101101001011010110010100110110110?01001110101001010100111?010110011001001001101001110100101001100101101001001001101101001111100110100110010110011101100000100110111010001010011001101001011?1110011011101010010111001101101101101001010010001001011011001?010011001011110010?1100101?011...

output:

17104
869248
19664
56
198080
5168
12128
165472
65488
10
2716
913
385472
885248
50608
585
1760
14
356416
27440
185888
72336
1311
1794
438080
417472
1995
224
56432
270400
978
619
170624
402048
371520
416704
409728
85072
333632
1749
67568
26992
314688
1073
417216
406464
317248
897920
826368
52688
89459...

result:

ok 1000 numbers

Test #35:

score: 5
Accepted
time: 4ms
memory: 22156kb

input:

500 1000
01100011001011011100101100110100110010110100010011010110011010010010110100100110010011001011001101001011001101001?110100101100011010011001011001101001011011?01001011010000101100110100101101100110101100110100101101001100101100110010110011011000011011001011000011010010110100101100111001011001...

output:

165248
67
67800
12312
6642
173728
129888
3724
44680
59112
343
2285
2628
356640
5150
74520
651
7544
2299
23680
32548
3908
3919
337952
682
119008
123024
276
13148
33452
8254
70552
7082
799
10000
734
170048
367136
1470
398
2127
14100
763
182688
350560
804
62088
10108
365472
16168
11136
66
2347
56664
15...

result:

ok 1000 numbers

Test #36:

score: 5
Accepted
time: 4ms
memory: 22220kb

input:

500 1000
0110100110010110100101?00110100101101001100101100101101001100101100110100110010110101001011001101010100?100101101001011001101001100101100110100101101001100101101001011001101001011010011001011001101001100101101001011001101001100?0110011010110100110010110011010010110?001100101100110?001100101...

output:

393
233816
97288
178160
157752
521488
7155
2230
429616
78500
29384
192248
13936
22126
1952
103352
547504
165400
722032
39936
6616
1335584
3086016
65036
278
91692
619024
96060
62792
198512
642160
20596
627120
16676
1248096
356616
4303
79340
229120
570368
28
5047
11090
36716
1276320
1454432
17460
1160...

result:

ok 1000 numbers

Subtask #7:

score: 5
Accepted

Test #37:

score: 5
Accepted
time: 5ms
memory: 26412kb

input:

1000 2000
01100101101001011001101001011010011001011010010110011010011001011001101001011010011001011010010110011010000110100101101001100101100110100110010110100101100110100110010110011010010110100110010110100101100110100101101001100101100110100110010110100101100110100101101001100101101001011001101001...

output:

3240
660160
644768
11858784
5776
12121
11513184
618368
615968
283884
287756
131958
136654
688720
16592
16444
585256
11476064
5050
591504
106490
114470
137158
1596
6031
5648304
11535200
111930
4278
11445472
51501
11529312
1770
50069
137226
8806
139654
5686
1891
22402
19931
138610
107750
51709
117090
...

result:

ok 2000 numbers

Test #38:

score: 5
Accepted
time: 2ms
memory: 26344kb

input:

1000 2000
010000101101000010011011001?111011010010101100110010110010010110011001011011110010111001011011001001110100101100110100000100110100100110110010101100110100110101100110100110010110010101101001100010011010101011010010100110?001001101110010110100100101011010011101001111110100110011010101011001...

output:

36508
1032896
1090624
6
9394
1164
216576
987968
6772
1376
21
26580
2206
39060
1938
2464
1002560
36308
3094
1063744
3042
39804
26020
3234
988480
34740
40740
2380
1100224
718
1063744
1060800
451648
34076
7342
3308
21716
9366
2066
38796
37828
463680
491392
473984
214720
26916
453824
24692
1027392
1702
...

result:

ok 2000 numbers

Test #39:

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

input:

1000 2000
0110100011010011001011100?01111010011001011001001011010100011001100100?011000011001011001101001011010011011001011100101100110100101101001100101100110100110010110100101110100110100110100110010011001011010001010100110010110011001100101101001010110100101010101001100101100101001011001101001100...

output:

989
34652
26512
40236
53876
51268
54464
54508
56676
33632
11404
17288
5168
34224
127692
42724
27324
917
59220
54360
45664
127748
39988
10760
55776
31204
54428
18512
51836
53996
122368
8964
125652
31764
3520
42364
41944
711
127780
127164
4244
45848
54996
3
123124
44644
11488
57544
51016
17984
30840
3...

result:

ok 2000 numbers

Test #40:

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

input:

1000 2000
01100110100110010110100101100110100101101001100001011010010110011010010110100110010110100101100110100110010110011010010110100110010110100101100110100101101001100101100110100110011010010110100110010110011010011001011010010110011010011001011001100101101001101001011010011001011010010110011010...

output:

231
2210
13703
1672512
55498
1907568
60184
1886352
261516
1756608
12639
12734
1409072
70520
1541952
11132
1685808
21
284252
11707
2669
1174
1490544
1802544
259548
1917168
2507
227164
9809
261516
332836
1572912
1207
331780
1751664
680576
2782
1913328
1942512
671608
332836
2257
1464624
1873472
1467072...

result:

ok 2000 numbers

Test #41:

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

input:

1000 2000
1101001100101001100101100110100101101001101100110100110010110011010010110100110010110100101100110100110010110100101101010011001011010001011001101001011010011001011010010011010010110011010010110010110100110010100110010110100101100110100110010110011010011?010110011010010110100110010110011010...

output:

4543
4732
134104
68168
2925
116176
133168
691200
114720
126656
4421
110752
1490496
324576
98536
114664
62472
3501
75488
129424
89408
29512
13318
91
123344
126504
100
205
60480
27052
128632
131200
1587456
1678656
83848
704832
69608
5263
128648
1457856
4577
128424
120936
1451968
705728
296032
1618368
...

result:

ok 2000 numbers

Test #42:

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

input:

1000 2000
00101101001011001101001011010011001011010?1011001101001100?01100110100101101001100101101?0101100110100101101001101100110100110010110100101100110100110010110011010010110100110010110011010011001011010010110011010010110100010110100101100110100?1001011001101001011010011001011010010110011010010...

output:

34744992
4054912
38220
506120
8568032
4141440
4143808
3505952
800000
1927232
73860
17225056
31668
2151632
8740
19180
630
25944
4097440
2528896
629960
3380600
26564
815096
2068240
20092
34597920
3882640
34679232
34620
2037496
4066240
36092128
3244360
4002896
351
35317408
171072
178176
1755152
6892
35...

result:

ok 2000 numbers

Subtask #8:

score: 10
Accepted

Test #43:

score: 10
Accepted
time: 64ms
memory: 29968kb

input:

5000 100000
????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????...

output:

917236499
938990217
971022999
554851016
181715280
908599565
546691770
255642236
350632401
637866763
166343858
683033814
718229119
422838464
146119838
444951922
65736136
508960351
784761148
970445740
912502388
852274767
253648149
877018129
621855209
790344143
522918273
37396133
247133429
795717452
85...

result:

ok 100000 numbers

Test #44:

score: 10
Accepted
time: 27ms
memory: 30400kb

input:

5000 100000
100101101001?1100?01011000101?0100101100110101101?0111?1101001011001101001010110011?1001?0010?1010010110011?1001011010011001101001011?011?10010110100110?101100110100110010110100100010110?1101001100101?0010110?00?100001011010011001011010?10110100011010010001?011110100110010?1010010?1?0110...

output:

181333203
591414383
589254303
940757793
510083804
174718411
721419168
15
768682772
647823182
958920107
830627476
651202642
901006181
361853307
92174151
604898967
237679107
1424896
556208572
234
898368017
790878450
375335223
226418218
28807656
641728259
231958166
581593907
320195917
757180541
4074822...

result:

ok 100000 numbers

Test #45:

score: 10
Accepted
time: 34ms
memory: 30160kb

input:

5000 100000
100101?01001011001101001100101100110100101101001100101100110100110010110100101100110100110010110011010010110100110010110100101100110100101101001100101100110100110010110100101100110100101101001100101101001011001101001100101100110100101101001100101101001011001101001011010011001011001101001...

output:

67824955
209117118
379438655
114306878
295248895
164227
146585824
19325496
1563698
130413792
97251710
979743871
366201151
36530
1740546
18730808
17162400
355493695
1572854
88845024
823394364
491714
776288255
137947
502058
484334
1271178
137492704
152824635
1679138
309568063
352055615
110175904
36316...

result:

ok 100000 numbers

Test #46:

score: 10
Accepted
time: 26ms
memory: 30372kb

input:

5000 100000
00101100110100110010111?10011?010011001111001101100110100101100110100110100110110011010011?01011101?010110100110010110100101?001101110100110010110011011001100010?010100110001101001011010010011001010011001011010110011010010101001100101101010010110010011101001100101100111110001101001100101...

output:

41941535
451313664
325919583
995930712
132719207
706248110
321992450
176117106
449806336
494098697
113472
206105860
879041541
820116607
629145591
134086654
779638211
322347544
102491949
849346519
218693810
88865164
350072291
162529271
777885434
486233063
199327469
970909370
805661366
162432
156096
9...

result:

ok 100000 numbers

Test #47:

score: 10
Accepted
time: 35ms
memory: 28776kb

input:

5000 100000
????????011??11?????1?0??????0?????0???0?00?0???10011001???0?0???1?0?11??001???????????0????01???001?001???010???110?110??0?0??0?0???0?1?11???1??0?11????1??1?0?0?????1??0?1?0010????11??00?0??01???100?0???01???????????????0?10????11?10?????01?01??1??????01??1?001?1?0?1?0?0???0?1?1101?0?01...

output:

653124428
472887592
193320531
47890176
349731052
47230205
400969322
364849857
556608253
806506705
403374118
941100958
654215111
674248493
552539335
458428844
507136873
459063360
253736841
286085933
145547659
443124539
262125212
626543796
681499574
640373630
581820872
411594429
615784351
473953763
44...

result:

ok 100000 numbers

Test #48:

score: 10
Accepted
time: 28ms
memory: 28112kb

input:

5000 100000
?11?0?011010010110?11010010?10?0011?0??1100??010?110010110?001011001??100?1001011?0110100101101001100?0110?11?10?1?00101101?01011001101001011010?11001?11?1?010110?11010?11?01?110?1?01?01?110?001?0010110?1??10011?010110100101?00110100110?101100110??0?011??00110?101?01?0?01100110100?011010...

output:

91564069
897007407
706959376
278669394
613293550
837689449
45709899
987558693
275114262
881129495
47373195
756575984
315811688
339142876
541580572
400055423
137120594
591840949
865650499
685939705
68735929
370750588
141952703
169253903
68431432
277638902
58437638
163456395
892081690
855754743
613985...

result:

ok 100000 numbers

Subtask #9:

score: 15
Accepted

Test #49:

score: 15
Accepted
time: 238ms
memory: 46288kb

input:

20000 100000
????????????????????????????0??????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????...

output:

797690592
461052157
366156716
681469086
68289270
998075042
417044714
305236310
486111979
31170382
205645653
175327903
424931979
288700215
752834615
40780625
840968759
440823348
361102633
349610855
524260600
389366747
592885315
42671444
854300072
42025735
229205663
827317741
367322959
727847372
63693...

result:

ok 100000 numbers

Test #50:

score: 15
Accepted
time: 82ms
memory: 33368kb

input:

20000 100000
001011001101001011010011001011011001101001100101101001011001101001100101100?101001011010011001011010010?1001101001011010011001?11001101001100010110100101100110100?10010110011010?1011??00?10010110100100110011010010?1010011001011001101001100101101001011001101001100101100110100101101001100...

output:

509364549
69312293
250873615
45312001
548205624
932693664
930304521
260510107
924144801
17320418
284019271
933809256
120015663
328187999
797497377
182927099
175155310
382927650
8240128
522090813
273821863
484244427
6238632
815475705
553529359
113889183
401510039
606004383
691584280
119549226
4192056...

result:

ok 100000 numbers

Test #51:

score: 15
Accepted
time: 75ms
memory: 32172kb

input:

20000 100000
01011001101001100101100110100101101001100101101001011001101001011010011001011001101001100101101001011001101001011010011001011010010110011010011001011001101001011010011001011001101001100101101001011001101001100101100110100101101001100101101001011001101001011010011001011001101001100101101...

output:

5969827
4639308
268121840
17799408
775227916
269745
477060634
571236487
313371312
834164739
2995032
542725724
419157563
14429336
287418958
559923706
379983646
5533294
81907967
410197
335936389
616019328
209860203
757876928
405985466
752549103
191963691
888024014
648492681
34692852
6648120
109807054
...

result:

ok 100000 numbers

Test #52:

score: 15
Accepted
time: 80ms
memory: 29852kb

input:

20000 100000
010110011010011001011010?1010010110100110010110110100101101001100101101001001011001101001011010011001011001101001111010010110011010011001011001101001011010011001011001011100110100101101110011010011001011010010110011010010110101011001101001011010100101100?10100110010110011110011010010110...

output:

867559954
728895265
8575872
2619456
3320192
322545062
805962835
222296813
451900787
863989933
889023846
782101874
839144061
110250362
620734346
662067120
589326158
625762289
811333669
737401372
882107104
125024
373233232
759422213
811362940
163948165
833093578
872426127
1371392
906682025
181236248
7...

result:

ok 100000 numbers

Test #53:

score: 15
Accepted
time: 99ms
memory: 33996kb

input:

20000 100000
??0??0100110?10?1????01?0?0?10??0?1?01??1??1??10??10??0?1010010?10?1??1??10?101001?00101??1001?1100?1?1001?00101?00??010?1011010????0???101001?????1????0??1101?01100?0?10?1?0?????00??1?0?001??10?11??0?101??1??110?1?110???10?100???10011?01?1?0?110?00?0?10?0?11?01?110??101???100?0?1?10010...

output:

417604375
405830950
483817482
615262841
249676247
537001048
273295838
239053590
988319082
966920667
341570059
870628103
979602834
163401628
395724519
695684486
279157180
463709487
989460660
407659939
821790731
441133283
187045625
935793626
163820305
505492574
169589457
154628740
463121217
305115019
...

result:

ok 100000 numbers

Test #54:

score: 15
Accepted
time: 83ms
memory: 33788kb

input:

20000 100000
?0110011??0010110?0?11001?11?01?010?11??1??1010?1011?0110100110010?10011010?101?010??10?101?010?1?110011?100101??1001100?011?0110100?100101101001?11001??10011001011?01101?010110??0110010110011?1001?00101101001011001?010010110100110010110100101100110100?1001?11?01101??1011010011001011?10...

output:

341207569
651719768
639293738
157425446
733087022
174930897
524255318
59417393
931738266
73255482
215557454
724814627
909954543
550020411
685072967
412129467
20205269
942857311
378562564
383261826
479700849
839278833
878122061
575239834
192638193
125593168
693678832
708479651
105751717
593635039
779...

result:

ok 100000 numbers

Subtask #10:

score: 20
Accepted

Test #55:

score: 20
Accepted
time: 215ms
memory: 41200kb

input:

50000 200000
?01101001011001?01?011?010?1001101001?110?001?0?1?1?001101?0110?101?010??01100110?00?1001011001101001011??001?001?110100101100110100101?01?0110?1011?011010011001?1?0100??110011?100?01101001100?011010?10??00110100?1?0?0110?1101?01??1?10??10010?10?00101?00??0???101101?0???010110??1?10011?...

output:

536829500
661251387
659588534
318023575
898544321
314654200
543259874
258689631
489123565
439731597
827775414
129256973
404486391
336314531
548004667
996947027
465782218
989450137
902043764
722858591
98820098
657243279
398977330
570470342
475874000
877038771
458243064
838873419
689121130
372167525
7...

result:

ok 200000 numbers

Test #56:

score: 20
Accepted
time: 264ms
memory: 46916kb

input:

50000 200000
1?0?101???1?01?01??010?1?10???0?????1????1??0???10???10??1??1??1001??0????01???1???011??1????00??????1010????????1001?1?0?01?010???1???1???0??00???0??????10?10?001????????1???????1???????01?1?0??00??1?????11?10??????1?1?0??11000110??????00????0?1??1??0?0???0???????0?1?1???????1????0?0??...

output:

408790848
273505216
338522743
120187302
390569627
475929073
507268158
942339285
917006323
594892242
280678170
939580236
858848067
279680778
53986925
138750144
856647448
709922142
790089395
789742255
593010279
136729508
110008361
386624134
149088071
433763168
285043168
104414082
322652355
884935065
9...

result:

ok 200000 numbers

Test #57:

score: 20
Accepted
time: 756ms
memory: 77000kb

input:

50000 200000
???????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????...

output:

312016077
857215004
341131961
775128919
262516889
197373454
496260099
857484489
945645760
808042444
883337590
330721082
433943003
634739702
831699725
17260301
450717299
921835274
283125773
385462161
274228879
616595673
283958300
600853407
457078999
832971967
910081505
674732247
259145597
116736774
9...

result:

ok 200000 numbers

Test #58:

score: 20
Accepted
time: 225ms
memory: 40088kb

input:

50000 200000
10010110011010010110100?1000101100110100101101001?0?101100110100?10010110100??1100110100101101001100?0110100101?0011010010110100101?00110?00110010010110011010011010011001011001?01001100101101001011?01101001100101100110100101101001100101101001011101001??10011010011001011001101001011?1001...

output:

125651881
428057479
320060234
322481595
980355350
598060608
225069942
38268314
447408506
423615088
469860617
713266537
327854546
738791313
114807387
923441462
353398008
705160508
978644481
744537690
110327237
247376105
466623433
626962700
931121443
230841293
339427058
679821123
865787785
380577809
3...

result:

ok 200000 numbers

Test #59:

score: 20
Accepted
time: 187ms
memory: 39916kb

input:

50000 200000
0100110010110100101100110100110010110011010011001?1100110100?011010011001011010010110011010010110100?1001011001101001100101101001011001101001011010011001011010010110?1101001100101100110100101?010011001110100101101001100101101001011001101001011010011001011001101001100101101001011001?0100...

output:

948852980
123778389
920122475
947693448
222058753
362055451
61028450
559265697
89763123
324198936
86217005
585119991
476610444
217407318
376690123
764170498
946651606
515570572
239434318
334520185
709072512
16483584
278883753
431049039
486077943
662772085
81107991
616301621
672863909
643174225
30744...

result:

ok 200000 numbers

Test #60:

score: 20
Accepted
time: 198ms
memory: 39728kb

input:

50000 200000
110100110010110100101100110100110010110011010010110100?10010110100101100110100101101001100101100110100110010110100?0110011010011001011001101001011010011001011001101001100101101001011001101001011010011001011010010110011010011001011001101001011010011001011010010110011010010110100110010110...

output:

795954535
912366093
895221479
804625705
152391382
55572690
283716731
930900486
598510661
479885373
582409215
551933334
655792652
672789223
258826084
344840482
34378898
341849236
368775804
579033109
517700876
74801968
212923886
625162799
440258160
517644815
444026092
889357720
404095791
684544237
589...

result:

ok 200000 numbers

Test #61:

score: 20
Accepted
time: 719ms
memory: 89336kb

input:

50000 200000
???????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????...

output:

163839168
511670061
181094521
974487131
586301784
3445303
959522424
262402444
387986975
771517253
916404026
185306709
628947008
872014418
974954210
615267488
551819065
310812085
327006588
445293012
770754719
95156069
693847850
520200196
778215040
694582455
28430744
996516939
638679658
566003992
7534...

result:

ok 200000 numbers

Test #62:

score: 20
Accepted
time: 193ms
memory: 39624kb

input:

50000 200000
11001101001011010011001011010010110011010011001011001010011001011010010110011010011001011001101101001100101101101001011001101001011010101100110100110010110100101100110100110011010001101001011010010101100010110011010011001010100110010110011010011001011010011001011011010010110100110010100...

output:

876556669
587581080
386911793
799845677
472585627
865627034
449128420
300864420
788522842
973889231
60608838
38672154
165856778
7767424
419422766
569835118
593923353
42398197
77271880
23069598
529844931
852924630
92101389
635697767
890361166
791341934
358907409
582837220
370040830
41133521
796664729...

result:

ok 200000 numbers

Test #63:

score: 20
Accepted
time: 231ms
memory: 43148kb

input:

50000 200000
110???11?0101???1??1?0101??1?0?1?0?0??00110??011???011??0010??00?1?1?0?011????????1?1?0100?0??0011010?110010?1001??100?01?0100?10?1011?1?01??1??1?01?010110100?1001???001??10?1??0?0?10100??11?011?1?0?0?10?0?110??01?01??10?10??1??0?1??0?01100?1?10?1011010????01?11?011?100110?1?110????0110...

output:

234091515
505792624
797513868
980793316
522011797
270839874
577493848
146647576
193190963
974317452
109492587
274269215
931767181
229385600
563178142
13739173
21724626
234805049
955969159
487614923
883118023
619638163
951429166
889896658
535991495
568167485
517310705
288279370
874600906
650124351
55...

result:

ok 200000 numbers

Test #64:

score: 20
Accepted
time: 215ms
memory: 41128kb

input:

50000 200000
?11?0101??01?0100110?10?10100?0?1001101001?0010?10?110?0010110100110?10?101?0?011001101001011010011?010110011010011001??1010??01100?1???0?01?0?00110?1?11010?10110011010?11001?1100110?00101101?01?00?01101001011001??100011?01011010?10?100110???1?11010?1100101101001011?01?0?00110010110011?...

output:

452246757
362654081
228585967
867476600
251403385
791316301
476903419
318688335
829611106
953566684
772528303
400507046
518746037
706671173
596580154
513865345
609102285
882388347
892953686
613674076
196614381
341296565
514481663
743727258
784986533
540368299
911123095
5592783
3513548
293707092
2967...

result:

ok 200000 numbers

Test #65:

score: 20
Accepted
time: 219ms
memory: 41520kb

input:

50000 200000
01?0100?101100101?0011010??01?010011?010110?1101001?0010110?00101100???100???001?1?110?1101?0?1001?1?01?010?100110?010?10?0011001?1?0100101100???1001?001???00?1010????1101001?11??0??1?01?1110?11?100?10010?10?110100010010110100?1?0?0110011?10?11001010110???0?00?1?0?01101001?1?0011010010?...

output:

477166228
170036549
442879037
617697483
621404949
70762376
978311633
940635763
826240127
626504821
458499206
599439469
987070289
407135938
143801187
78621934
936071377
740605936
457084884
326867352
80929407
908402752
968480883
63417872
171389430
866906035
493244799
104070656
694404189
379589072
5579...

result:

ok 200000 numbers

Test #66:

score: 20
Accepted
time: 196ms
memory: 39704kb

input:

50000 200000
0101101001100101101001011001101001100101100110100101101001100101101001011001101001011?100110010110011010011001011?100101?001101001011010011001011010010110011010011001011001101001011010011001?110011010011001011010010110011010011001011001101001011010011001011010010110011010010110100110010...

output:

790732344
539533104
896740883
362496960
673229437
493513005
280500453
674936961
112286251
2373824
954866476
136396192
874754107
947488885
590101655
569069397
521198920
750627150
14177006
110137892
533645196
771805672
330125610
963288951
268767225
8313288
307546819
86354971
119313966
610157348
360845...

result:

ok 200000 numbers
English 繁體中文 简体中文

服务器时间: 2024-12-05 02:24:03 | 开源项目