QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#411055#8352. 菱形覆盖Qingyu100 ✓1679ms150864kbC++232.8kb2024-05-14 20:51:542024-05-14 20:56:28

Judging History

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

  • [2024-05-14 20:56:28]
  • 管理员手动重测该提交记录
  • 测评结果:100
  • 用时:1679ms
  • 内存:150864kb
  • [2024-05-14 20:55:01]
  • 管理员手动重测该提交记录
  • 测评结果:0
  • 用时:1670ms
  • 内存:150560kb
  • [2024-05-14 20:53:51]
  • 管理员手动重测该提交记录
  • 测评结果:0
  • 用时:1686ms
  • 内存:118560kb
  • [2024-05-14 20:51:55]
  • 评测
  • 测评结果:0
  • 用时:1645ms
  • 内存:150436kb
  • [2024-05-14 20:51:54]
  • 提交

answer

#include<bits/stdc++.h>

#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,ll> pll;

template <typename T> bool chkmax(T &x,T y){return x<y?x=y,true:false;}
template <typename T> bool chkmin(T &x,T y){return x>y?x=y,true:false;}

int readint(){
	int x=0,f=1; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

struct node{
	int val,maxa;
}t[20000];

int n,sum;
int lf[5005][5005];
char s[5005][5005],ans[5005][5005];
vector<int> h[5005];

void update(int id){
	t[id].val=t[id<<1].val+t[id<<1|1].val;
	t[id].maxa=max(t[id<<1].maxa,t[id<<1|1].maxa+t[id<<1].val);
}

void build(int id,int l,int r){
	if(l==r) return (void)(t[id].val=t[id].maxa=1);
	int mid=(l+r)/2;
	build(id<<1,l,mid);
	build(id<<1|1,mid+1,r);
	update(id);
}

void change(int id,int l,int r,int x,int c){
	if(l==r) return (void)(t[id].val+=c,t[id].maxa+=c);
	int mid=(l+r)/2;
	if(x<=mid) change(id<<1,l,mid,x,c);
	else change(id<<1|1,mid+1,r,x,c);
	update(id);
}

int query(int id,int l,int r,int x){
	if(l==r) return l+1;
	int mid=(l+r)/2;
	if(t[id<<1].maxa>=x) return query(id<<1,l,mid,x);
	else return query(id<<1|1,mid+1,r,x-t[id<<1].val);
}

bool getleft(int i,int j){
	for(auto x:h[i-1]){
		if(x>j-i+1) break;
		change(1,1,n,x,-1);
		sum++;
	}
	if(sum>j-i+1) return false;
	if(sum==j-i+1) lf[j][j-i+1]=1;
	else{
		if(t[1].maxa<j-i+1-sum) lf[j][j-i+1]=j-i+2;
		else lf[j][j-i+1]=query(1,1,n,j-i+1-sum);
	}
	return true;
}

int main(){
	n=readint();
	for(int i=1;i<=n;i++) scanf("%s",s[i]+1);
	for(int i=0;i<=n;i++) h[i].clear();
	for(int i=1;i<=n;i++) for(int j=1;j<=i;j++) if(s[i][j]=='0') h[i-j].pb(j),ans[i][j]='-';
	bool fl=0;
	for(int i=n;i>=2;i--){
		vector<int> v(0);
		for(int j=1;j<=i;j++) if(s[i][j]=='0') v.pb(j);
		if(!v.size()){
			fl=1;
			break;
		}
		for(int j=1;j<v[0];j++) ans[i][j]='3';
		for(int j=v[v.size()-1]+1;j<=i;j++) ans[i][j]='1';
		build(1,1,n);
		sum=0;
		for(int j=1;j<v[0];j++){
			if(!getleft(i-j,i-1)){
				fl=1;
				break;
			}
		}
		if(fl) break;
		for(int j=1;j<v.size();j++){
			int p1=v[j-1],p2=v[j],pos=p1;
			for(int k=p1;k<p2;k++){
				if(!getleft(i-k,i-1)){
					fl=1;
					break;
				}
				if(lf[i-1][k]<=p1) pos=k+1;
			}
			if(fl) break;
			if(pos==p2){
				fl=1;
				break;
			}
			s[i-1][pos]='0';
			ans[i-1][pos]='2';
			change(1,1,n,pos,-1);
			sum++;
			for(int k=p1+1;k<=pos;k++) ans[i][k]='1';
			for(int k=pos+1;k<p2;k++) ans[i][k]='3';
		}
		if(fl) break;
	}
	if(fl){
		printf("Impossible!\n");
		return 0;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=i;j++) putchar(ans[i][j]);
		puts("");
	}
	return 0;
}

詳細信息

Subtask #1:

score: 5
Accepted

Test #1:

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

input:

5
0
00
111
1110
11011

output:

Impossible!

result:

ok ok

Test #2:

score: 0
Accepted
time: 1ms
memory: 7764kb

input:

5
1
01
110
0111
10011

output:

2
-2
21-
-211
3--11

result:

ok ok

Test #3:

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

input:

5
1
00
101
1110
11110

output:

2
--
3-1
333-
3333-

result:

ok ok

Test #4:

score: 0
Accepted
time: 1ms
memory: 8076kb

input:

5
1
11
101
0111
10100

output:

2
22
2-2
-212
3-3--

result:

ok ok

Test #5:

score: 0
Accepted
time: 1ms
memory: 7880kb

input:

5
1
11
011
0111
10010

output:

Impossible!

result:

ok ok

Subtask #2:

score: 10
Accepted

Dependency #1:

100%
Accepted

Test #6:

score: 10
Accepted
time: 1ms
memory: 8024kb

input:

10
0
01
111
1110
11011
111111
1111110
10101111
011111111
0111011111

output:

-
-1
211
233-
23-11
221111
223333-
2-3-1111
-21111111
-133-11111

result:

ok ok

Test #7:

score: 0
Accepted
time: 1ms
memory: 7884kb

input:

10
1
11
110
1011
11111
111110
1011011
11111100
110111111
1111011011

output:

Impossible!

result:

ok ok

Test #8:

score: 0
Accepted
time: 1ms
memory: 8028kb

input:

10
1
01
110
1111
11111
011111
1011011
11011111
111111110
1101001111

output:

2
-2
21-
2211
22211
-22211
3-22-11
33-22111
33212333-
33-3--1111

result:

ok ok

Test #9:

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

input:

10
1
11
110
0011
11111
111001
1101011
11110111
111111101
0111111111

output:

2
22
22-
--21
33221
332--1
33-3-11
3333-111
3333333-1
-111111111

result:

ok ok

Test #10:

score: 0
Accepted
time: 1ms
memory: 7792kb

input:

10
0
11
111
1111
11101
010011
1111111
11111100
101110011
1111111111

output:

Impossible!

result:

ok ok

Subtask #3:

score: 35
Accepted

Dependency #2:

100%
Accepted

Test #11:

score: 35
Accepted
time: 2ms
memory: 10324kb

input:

500
1
11
111
1111
11111
111111
1111111
11111111
111111111
1111111111
11111111111
111111111111
1111111111111
11111111111111
111111111111111
1111111111111111
11111111111111111
111111111111111111
1111111111111111111
11111111111111111111
111111111111111111111
1111111111111111111111
111111111111111111111...

output:

Impossible!

result:

ok ok

Test #12:

score: 0
Accepted
time: 14ms
memory: 26200kb

input:

500
1
11
111
1111
11111
111111
1111111
11111111
111111111
1111111111
11111111111
111111111111
1111111111111
11111111111111
111111111111111
1111111111111111
11111111111111111
111111111111111111
1111111111111111111
11111111111111111111
111111111111111111111
1111111111111111111111
111111111111111111111...

output:

2
22
222
2222
22222
222222
2222222
22222222
222222222
2222222222
22222222222
222222222222
2222222222222
22222222222222
222222222222222
2222222222222222
22222222222222222
222222222222222222
2222222222222222222
22222222222222222222
222222222222222222222
2222222222222222222222
22222222222222222222222
2...

result:

ok ok

Test #13:

score: 0
Accepted
time: 13ms
memory: 21544kb

input:

500
1
11
111
1111
01111
111111
1111111
11111111
111111111
1111111111
11111111111
111111111111
1111111111111
11111111111111
111111111111111
1111111111111111
11111111111111111
111111101111111111
1111111011111111111
11111111111111111111
111111111111111111111
1111111111111111111111
111111111111111111111...

output:

2
22
222
2222
-2222
322222
3222222
32222222
322222222
3222222222
32222222222
322222222222
3222222222222
32222222222222
322222222222222
3222222222222222
32222222222222222
3222222-2222222222
3222222-12222222222
32222222112222222222
322222222112222222222
3222222222112222222222
32222222222112222222222
3...

result:

ok ok

Test #14:

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

input:

500
1
11
111
1111
11111
111111
1111011
11111111
111111111
1111111111
11111111111
111111111111
1111111111111
11111111111111
011111111111111
1111111111111111
11111111111111111
111111111111111111
1111111111111111111
11111111111111111111
111111111111111111111
1111111111111111111111
111111111111111111111...

output:

Impossible!

result:

ok ok

Test #15:

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

input:

500
1
11
111
1111
11111
111111
1111111
11111111
111111111
1111111111
11111111111
111111111111
1111110111111
11111111111111
111111111111111
1111111111110111
11111111111111111
111111111111111111
1111111111111111111
11111111111111111111
111111111111111111110
1111111111111111111111
111111111111111111111...

output:

Impossible!

result:

ok ok

Test #16:

score: 0
Accepted
time: 14ms
memory: 23992kb

input:

500
1
11
111
1111
11111
111111
1111111
11111111
111111111
1111111111
11111111111
111111111111
1111111111111
11111111111111
111111111111111
1111111111111111
11111111111111111
111111111111111111
1111111111111111111
11111111111111111111
111111111111111111111
1111111111111111111111
111111111111111111111...

output:

2
22
222
2222
22222
222222
2222222
22222222
222222222
2222222222
22222222222
222222222222
2222222222222
22222222222222
222222222222222
2222222222222222
22222222222222222
222222222222222222
2222222222222222222
22222222222222222222
222222222222222222222
2222222222222222222222
22222222222222222222222
2...

result:

ok ok

Test #17:

score: 0
Accepted
time: 9ms
memory: 23172kb

input:

500
1
11
111
1111
11111
111111
1111111
11111111
111111111
1111111111
11111111111
111111111111
1111111111111
11111111111111
111111111111111
1111111111111111
11111111111101111
111111111111111111
1111111111111111111
11111111111111111111
111111111111111111111
1111111111111111111111
111111111111111111111...

output:

2
22
222
2222
22222
222222
2222222
22222222
222222222
2222222222
22222222222
222222222222
2222222222222
22222222222222
222222222222222
2222222222222222
222222222222-2222
222222222222212222
2222222222222212222
22222222222222212222
222222222222222212222
2222222222222222212222
22222222222222222212222
2...

result:

ok ok

Test #18:

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

input:

500
1
11
111
1111
11111
111111
1111111
11111111
111111111
1111111111
11111111111
111111111111
1111111111111
11111111111111
111111111111111
1111111111111111
11111111111111111
111111111111111111
1111111111111111111
11111111111111111111
111111111111111111111
1111111111111111111111
111111111111111111111...

output:

2
22
222
2222
22222
222222
2222222
22222222
222222222
2222222222
22222222222
222222222222
2222222222222
22222222222222
222222222222222
2222222222222222
22222222222222222
222222222222222222
2222222222222222222
22222222222222222222
222222222222222222222
2222222222222222222222
22222222222222222222222
2...

result:

ok ok

Test #19:

score: 0
Accepted
time: 6ms
memory: 23924kb

input:

500
1
11
111
1111
11111
111111
1111111
11111111
111111111
1111111111
11111111111
111111111111
1111111111111
11111111111111
111111111111111
1111111111111111
11111111111111111
111111111111111111
1111111111111111111
11111111111111111111
111111111111111111111
1111111111110111111111
111111111111111111111...

output:

2
22
222
2222
22222
222222
2222222
22222222
222222222
2222222222
22222222222
222222222222
2222222222222
22222222222222
222222222222222
2222222222222222
22222222222222222
222222222222222222
2222222222222222222
22222222222222222222
222222222222222222222
222222222222-222222222
22222222222221222222222
2...

result:

ok ok

Test #20:

score: 0
Accepted
time: 9ms
memory: 21612kb

input:

500
1
11
111
1111
11111
111111
1111111
11111111
111111111
1111111111
11111111111
111111111111
1111111111111
11111111111111
111111111111111
1111111111111111
11111111111111111
111111111111111111
1111101111111111111
11111111111111111111
111111111111111111111
1111111111111111111111
111111111111111111111...

output:

2
22
222
2222
22222
222222
2222222
22222222
222222222
2222222222
22222222222
222222222222
2222222222222
22222222222222
222222222222222
2222222222222222
22222222222222222
222222222222222222
22222-2222222222222
22222212222222222222
222222212222222222222
2222222212222222222222
22222222212222222222222
2...

result:

ok ok

Test #21:

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

input:

500
1
11
111
1111
11111
111111
1111111
11111111
111111111
1111111111
11111111111
111111111111
1111111111111
11111111111111
111111111111111
1111111111111111
11111111111111111
111111111111111111
1111111111111111111
11111111111111111111
111111111111111111111
1111111111111111111111
111111111111111111111...

output:

2
22
222
2222
22222
222222
2222222
22222222
222222222
2222222222
22222222222
222222222222
2222222222222
22222222222222
222222222222222
2222222222222222
22222222222222222
222222222222222222
2222222222222222222
22222222222222222222
222222222222222222222
2222222222222222222222
22222222222222222222222
2...

result:

ok ok

Test #22:

score: 0
Accepted
time: 7ms
memory: 26656kb

input:

500
1
11
111
1111
11111
111111
1111111
11111111
111111111
1111111111
11111111111
111111111111
1111111111111
11111111111111
111111111111111
1111111111111111
11111111111111111
111111111111111111
1111111111111111111
11111111111111111111
111111111111111111111
1111111111111111111111
111111111111111111111...

output:

2
22
222
2222
22222
222222
2222222
22222222
222222222
2222222222
22222222222
222222222222
2222222222222
22222222222222
222222222222222
2222222222222222
22222222222222222
222222222222222222
2222222222222222222
22222222222222222222
222222222222222222222
2222222222222222222222
22222222222222222222222
2...

result:

ok ok

Test #23:

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

input:

500
1
11
111
1111
11111
111111
1111111
11111111
111111111
1111111111
11111111111
111111111111
1111111111111
11111111111111
111111111111111
1111111111111111
11111111111111111
111111111111111111
1111111111111111111
11111111111111111111
111111111111111111111
1111111111111111111111
111111111111111111111...

output:

2
22
222
2222
22222
222222
2222222
22222222
222222222
2222222222
22222222222
222222222222
2222222222222
22222222222222
222222222222222
2222222222222222
22222222222222222
222222222222222222
2222222222222222222
22222222222222222222
222222222222222222222
2222222222222222222222
22222222222222222222222
2...

result:

ok ok

Test #24:

score: 0
Accepted
time: 13ms
memory: 22776kb

input:

500
1
11
111
1111
11111
111111
1111111
11111111
111111111
1111111111
11111111111
111111111111
1111111111111
11111111111111
111111111111111
1111111111111111
11111111111111111
111111111111111111
1111111111111111111
11111111111111111111
111111111111111011111
1111111111111111111111
111111111111111111111...

output:

2
22
222
2222
22222
222222
2222222
22222222
222222222
2222222222
22222222222
222222222222
2222222222222
22222222222222
222222222222222
2222222222222222
22222222222222222
222222222222222222
2222222222222222222
22222222222222222222
222222222222222-22222
2222222222222222122222
22222222222222222122222
2...

result:

ok ok

Test #25:

score: 0
Accepted
time: 8ms
memory: 26148kb

input:

500
1
11
111
1111
11111
111111
1111111
11111111
111111111
1111111111
11111111111
111111111111
1111111111111
11111111111111
111111111111111
1111111111111111
11111111111111111
111111111111111111
1111111111111111111
11111111111101111111
111111111111111111111
1111111111111111111111
111111111111111111111...

output:

2
22
222
2222
22222
222222
2222222
22222222
222222222
2222222222
22222222222
222222222222
2222222222222
22222222222222
222222222222222
2222222222222222
22222222222222222
222222222222222222
2222222222222222222
222222222222-2222222
222222222222212222222
2222222222222212222222
22222222222222212222222
2...

result:

ok ok

Subtask #4:

score: 5
Accepted

Test #26:

score: 5
Accepted
time: 709ms
memory: 150260kb

input:

5000
0
10
101
1101
01111
111101
1111011
11111101
111111101
1111111011
11101111111
101111111111
1111011111111
11111111111011
111011111111111
1111111111111101
11111111110111111
111111111011111111
1111101111111111111
11111111101111111111
111111111111110111111
1111111111111111101111
11110111111111111111...

output:

-
3-
3-1
33-1
-1111
3333-1
3333-11
333333-1
3333333-1
3333333-11
333-1111111
3-1111111111
3333-11111111
33333333333-11
333-11111111111
33333333333333-1
3333333333-111111
333333333-11111111
33333-1111111111111
333333333-1111111111
33333333333333-111111
33333333333333333-1111
3333-111111111111111111
3...

result:

ok ok

Test #27:

score: 0
Accepted
time: 689ms
memory: 150280kb

input:

5000
0
10
110
1110
11011
111101
1111011
11111110
111111110
1111110111
11111110111
111111111011
1111111101111
11111011111111
111110111111111
1110111111111111
11111111011111111
111111111111110111
0111111111111111111
11111111111111110111
111111111111111101111
1111111011111111111111
11111111110111111111...

output:

-
3-
33-
333-
33-11
3333-1
3333-11
3333333-
33333333-
333333-111
3333333-111
333333333-11
33333333-1111
33333-11111111
33333-111111111
333-111111111111
33333333-11111111
33333333333333-111
-111111111111111111
3333333333333333-111
3333333333333333-1111
3333333-11111111111111
3333333333-111111111111
3...

result:

ok ok

Test #28:

score: 0
Accepted
time: 678ms
memory: 150696kb

input:

5000
0
01
110
1011
11101
111011
1101111
11111011
111101111
1111011111
10111111111
111111110111
1110111111111
11111111101111
111111111011111
1111111111111011
11111111111101111
111111111111011111
1111111111111111011
11111111110111111111
111111111111111011111
1111110111111111111111
11111111111111111101...

output:

-
-1
33-
3-11
333-1
333-11
33-1111
33333-11
3333-1111
3333-11111
3-111111111
33333333-111
333-111111111
333333333-1111
333333333-11111
3333333333333-11
333333333333-1111
333333333333-11111
3333333333333333-11
3333333333-111111111
333333333333333-11111
333333-111111111111111
333333333333333333-1111
3...

result:

ok ok

Subtask #5:

score: 15
Accepted

Test #29:

score: 15
Accepted
time: 1679ms
memory: 150500kb

input:

5000
1
11
111
1111
11111
111111
1111111
11111111
111111111
1111111111
11111111111
111111111111
1111111111111
11111111111111
111111111111111
1111111111111111
11111111111111111
111111111111111111
1111111111111111111
11111111111111111111
111111111111111111111
1111111111111111111111
11111111111111111111...

output:

2
22
222
2222
22222
222222
2222222
22222222
222222222
2222222222
22222222222
222222222222
2222222222222
22222222222222
222222222222222
2222222222222222
22222222222222222
222222222222222222
2222222222222222222
22222222222222222222
222222222222222222222
2222222222222222222222
22222222222222222222222
2...

result:

ok ok

Test #30:

score: 0
Accepted
time: 1393ms
memory: 150864kb

input:

5000
1
11
111
1111
11111
111111
1111111
11111111
111111111
1111111111
11111111111
111111111111
1111111111111
11111111111111
111111111111111
1111111111111111
11111111111111111
111111111111111111
1111111111111111111
11111111111111111111
111111111111111111111
1111111111111111111111
11111111111111111111...

output:

2
22
222
2222
22222
222222
2222222
22222222
222222222
2222222222
22222222222
222222222222
2222222222222
22222222222222
222222222222222
2222222222222222
22222222222222222
222222222222222222
2222222222222222222
22222222222222222222
222222222222222222222
2222222222222222222222
22222222222222222222222
2...

result:

ok ok

Test #31:

score: 0
Accepted
time: 1306ms
memory: 150388kb

input:

5000
1
11
111
1111
11111
111111
1111111
11111111
111111111
1111111111
11111111111
111111111111
1111111111111
11111111111111
111111111111111
1111111111111111
11111111111111111
111111111111111111
1111111111111111111
11111011111111111111
111111111111111111111
1111111111111111111111
11111111111111111111...

output:

2
22
222
2222
22222
222222
2222222
22222222
222222222
2222222222
22222222222
222222222222
2222222222222
22222222222222
222222222222222
2222222222222222
22222222222222222
222222222222222222
2222222222222222222
22222-22222222222222
222222122222222222222
2222222122222222222222
22222222122222222222222
2...

result:

ok ok

Test #32:

score: 0
Accepted
time: 1339ms
memory: 150424kb

input:

5000
1
11
111
1111
11111
111111
1111111
11111111
111111111
1111111111
11111111111
111111111111
1111111111111
11111111111111
111111111111111
1111111111111111
11111111111111111
111111111111111111
1111111111111111111
11111111111111111111
111111111111111111111
1111111111111111111111
11111111111111111111...

output:

2
22
222
2222
22222
222222
2222222
22222222
222222222
2222222222
22222222222
222222222222
2222222222222
22222222222222
222222222222222
2222222222222222
22222222222222222
222222222222222222
2222222222222222222
22222222222222222222
222222222222222222222
2222222222222222222222
22222222222222222222222
2...

result:

ok ok

Test #33:

score: 0
Accepted
time: 1380ms
memory: 150520kb

input:

5000
1
11
111
1111
11111
111111
1111111
11111111
111111111
1111111111
11111111111
111111111111
1111111111111
11111111111111
111111111111111
1111111111111111
11111111111111111
111111111111111111
1111111111111111111
11111111111111111111
111111111111111111111
1111111111111111111111
11111111111111111111...

output:

2
22
222
2222
22222
222222
2222222
22222222
222222222
2222222222
22222222222
222222222222
2222222222222
22222222222222
222222222222222
2222222222222222
22222222222222222
222222222222222222
2222222222222222222
22222222222222222222
222222222222222222222
2222222222222222222222
22222222222222222222222
2...

result:

ok ok

Subtask #6:

score: 30
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Dependency #5:

100%
Accepted

Test #34:

score: 30
Accepted
time: 519ms
memory: 77416kb

input:

5000
1
11
111
1111
11111
111111
1111111
11111111
111111111
1111111111
11111111111
111111111111
1111111111111
11111111111111
111111111111111
1111111111111111
11111111111111111
111111111111111111
1111111111111111111
11111111111111111111
111111111111111111111
1111111111111111111111
11111111111111111111...

output:

Impossible!

result:

ok ok

Test #35:

score: 0
Accepted
time: 1475ms
memory: 150280kb

input:

5000
1
11
111
1111
11111
111111
1111111
11111111
111111111
1111111111
11111111111
111111111111
1111111111111
11111111111111
111111111111111
1111111111111111
11111111111111111
111111111111111111
1111111111111111111
11111111111111111111
111111111111111111111
1111111111111111111111
11111111111111111111...

output:

2
22
222
2222
22222
222222
2222222
22222222
222222222
2222222222
22222222222
222222222222
2222222222222
22222222222222
222222222222222
2222222222222222
22222222222222222
222222222222222222
2222222222222222222
22222222222222222222
222222222222222222222
2222222222222222222222
22222222222222222222222
2...

result:

ok ok

Test #36:

score: 0
Accepted
time: 1474ms
memory: 150488kb

input:

5000
1
11
111
1111
11111
111111
1111111
11111111
111111111
1111111111
11111111111
111111111111
1111111111111
11111111111111
111111111111111
1111111111111111
11111111111111111
111111111111111111
1111111111111111111
11111111111111111111
111111111111111111111
1111111111111111111111
11011111111111111111...

output:

2
22
222
2222
22222
222222
2222222
22222222
222222222
2222222222
22222222222
222222222222
2222222222222
22222222222222
222222222222222
2222222222222222
22222222222222222
222222222222222222
2222222222222222222
22222222222222222222
222222222222222222222
2222222222222222222222
22-22222222222222222222
2...

result:

ok ok

Test #37:

score: 0
Accepted
time: 652ms
memory: 87460kb

input:

5000
1
11
111
1111
11111
111111
1111111
11111111
111111111
1111111111
11111111111
111111111111
1111111111111
11111111111111
111111111111111
1111111111111111
11111111111111111
111111111111111111
1111111111111111111
11111111111111111111
111111111111111111111
1111111111111111111111
11111111111111111111...

output:

Impossible!

result:

ok ok

Test #38:

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

input:

5000
1
11
111
1111
11111
111111
1111111
11111111
111111111
1111111111
11111111111
111111111111
1111111111111
11111111111111
111111111111111
1111111111111111
11111111111111111
111111111111111111
1111111111111111111
11111111111111111111
111111111111111111111
1111111111111111111111
11111111111111111111...

output:

Impossible!

result:

ok ok

Test #39:

score: 0
Accepted
time: 1494ms
memory: 150640kb

input:

5000
1
11
111
1111
11111
111111
1111111
11111111
111111111
1111111111
11111111111
111111111111
1111111111111
11111111111111
111111111111111
1111111111111111
11111111111111111
111111111111111111
1111111111111111111
11111111111111111111
111111111111111111111
1111111111111111111111
11111111111111111111...

output:

2
22
222
2222
22222
222222
2222222
22222222
222222222
2222222222
22222222222
222222222222
2222222222222
22222222222222
222222222222222
2222222222222222
22222222222222222
222222222222222222
2222222222222222222
22222222222222222222
222222222222222222222
2222222222222222222222
22222222222222222222222
2...

result:

ok ok

Test #40:

score: 0
Accepted
time: 1450ms
memory: 150264kb

input:

5000
1
11
111
1111
11111
111111
1111111
11111111
111111111
1111111111
11111111111
111111111111
1111111111111
11111111111111
111111111111111
1111111111111111
11111111111111111
111111111111111111
1111111111111111111
11111111111111111111
111111111111111111111
1111111111111111111111
11111111111111111111...

output:

2
22
222
2222
22222
222222
2222222
22222222
222222222
2222222222
22222222222
222222222222
2222222222222
22222222222222
222222222222222
2222222222222222
22222222222222222
222222222222222222
2222222222222222222
22222222222222222222
222222222222222222222
2222222222222222222222
22222222222222222222222
2...

result:

ok ok

Test #41:

score: 0
Accepted
time: 1533ms
memory: 150560kb

input:

5000
1
11
111
1111
11111
111111
1111111
11111111
111111111
1111111111
11111111111
111111111111
1111111111111
11111111111111
111111111111111
1111111111111111
11111111111111111
111111111111111111
1111111111111111111
11111111111111111111
111111111111111111111
1111111111111111111111
11111111111111111111...

output:

2
22
222
2222
22222
222222
2222222
22222222
222222222
2222222222
22222222222
222222222222
2222222222222
22222222222222
222222222222222
2222222222222222
22222222222222222
222222222222222222
2222222222222222222
22222222222222222222
222222222222222222222
2222222222222222222222
22222222222222222222222
2...

result:

ok ok

Test #42:

score: 0
Accepted
time: 1323ms
memory: 150528kb

input:

5000
1
11
111
1111
11111
111111
1111111
11111111
111111111
1111111111
11111111111
111111111111
1111111111111
11111111111111
111111011111111
1111111111111111
11111111111111111
111111111111111111
1111111111111111111
11111111111111111111
111111111111111111111
1111111111111111111111
11111111111111111111...

output:

2
22
222
2222
22222
222222
2222222
22222222
222222222
2222222222
22222222222
222222222222
2222222222222
22222222222222
222222-22222222
2222222122222222
22222222122222222
222222222122222222
2222222222122222222
22222222222122222222
222222222222122222222
2222222222222122222222
22222222222222122222222
2...

result:

ok ok

Test #43:

score: 0
Accepted
time: 1297ms
memory: 150760kb

input:

5000
1
11
111
1111
11111
111111
1111111
11111111
111111111
1111111111
11111111111
111111111111
1111111111111
11111111111111
111111111111111
1111111111111111
11111111111111111
111111111111111111
1111111111111111111
11111111111111111111
111111111111111111111
1111111111111111111111
11111111111111111111...

output:

2
22
222
2222
22222
222222
2222222
22222222
222222222
2222222222
22222222222
222222222222
2222222222222
22222222222222
222222222222222
2222222222222222
22222222222222222
222222222222222222
2222222222222222222
22222222222222222222
222222222222222222222
2222222222222222222222
22222222222222222222222
2...

result:

ok ok

Test #44:

score: 0
Accepted
time: 1545ms
memory: 150540kb

input:

5000
1
11
111
1111
11111
111111
1111111
11111111
111111111
1111111111
11111111111
111111111111
1111111111111
11111111111111
111111111111111
1111111111111111
11111111111111111
111111111111111111
1111111111111111111
11111111111111111111
111111111111111111111
1111111111111111111111
11111111111111111111...

output:

2
22
222
2222
22222
222222
2222222
22222222
222222222
2222222222
22222222222
222222222222
2222222222222
22222222222222
222222222222222
2222222222222222
22222222222222222
222222222222222222
2222222222222222222
22222222222222222222
222222222222222222222
2222222222222222222222
22222222222222222222222
2...

result:

ok ok

Test #45:

score: 0
Accepted
time: 1333ms
memory: 150796kb

input:

5000
1
11
111
1111
11111
111111
1111111
11111111
111111111
1111111111
11111111111
111111111111
1111111111111
11111111111111
111111111111111
1111111111111111
11111111111111111
111111111111111111
1111111111111111111
11111111111111111111
111111111111111111111
1111111111111111111111
11111111111111111111...

output:

2
22
222
2222
22222
222222
2222222
22222222
222222222
2222222222
22222222222
222222222222
2222222222222
22222222222222
222222222222222
2222222222222222
22222222222222222
222222222222222222
2222222222222222222
22222222222222222222
222222222222222222222
2222222222222222222222
22222222222222222222222
2...

result:

ok ok

Test #46:

score: 0
Accepted
time: 1422ms
memory: 150816kb

input:

5000
1
11
111
1111
11111
111111
1111111
11111111
111111111
1111111111
11111111111
111111111111
1111111111111
11111111111111
111111111111111
1111111111111111
11111111111111111
111111111111111111
1111111111111111111
11111111111111111111
111111111111111111111
1111111111111111111111
11111111111111111111...

output:

2
22
222
2222
22222
222222
2222222
22222222
222222222
2222222222
22222222222
222222222222
2222222222222
22222222222222
222222222222222
2222222222222222
22222222222222222
222222222222222222
2222222222222222222
22222222222222222222
222222222222222222222
2222222222222222222222
22222222222222222222222
2...

result:

ok ok

Test #47:

score: 0
Accepted
time: 1420ms
memory: 150548kb

input:

5000
1
11
111
1111
11111
111111
1111111
11111111
111111111
1111111111
11111111111
111111111111
1111111111111
11111111111111
111111111111111
1111111111111111
11111111111111111
111111111111111111
1111111111111111111
11111111111111111111
111111111111111111111
1111111111111111111111
11111111111111111111...

output:

2
22
222
2222
22222
222222
2222222
22222222
222222222
2222222222
22222222222
222222222222
2222222222222
22222222222222
222222222222222
2222222222222222
22222222222222222
222222222222222222
2222222222222222222
22222222222222222222
222222222222222222222
2222222222222222222222
22222222222222222222222
2...

result:

ok ok

Test #48:

score: 0
Accepted
time: 1533ms
memory: 150512kb

input:

5000
1
11
111
1111
11111
111111
1111111
11111111
111111111
1111111111
11111111111
111111111111
1111111111111
11111111111111
111111111111111
1111111111111111
11111111111111111
111111111111111111
1111111111111111111
11111111111111111111
111111111111111111111
1111111111111111111111
11111111111111111111...

output:

2
22
222
2222
22222
222222
2222222
22222222
222222222
2222222222
22222222222
222222222222
2222222222222
22222222222222
222222222222222
2222222222222222
22222222222222222
222222222222222222
2222222222222222222
22222222222222222222
222222222222222222222
2222222222222222222222
22222222222222222222222
2...

result:

ok ok

Test #49:

score: 0
Accepted
time: 1320ms
memory: 150796kb

input:

5000
1
11
111
1111
11111
111111
1111111
11111111
111111111
1111111111
11111111111
111111111111
1111111111111
11111111111111
111111111111111
1111111111111111
11111111111111111
111111111111111111
1111111111111111111
11111111111111111111
111111111111111111111
1111111111111111111111
11111111111111111111...

output:

2
22
222
2222
22222
222222
2222222
22222222
222222222
2222222222
22222222222
222222222222
2222222222222
22222222222222
222222222222222
2222222222222222
22222222222222222
222222222222222222
2222222222222222222
22222222222222222222
222222222222222222222
2222222222222222222222
22222222222222222222222
2...

result:

ok ok

Test #50:

score: 0
Accepted
time: 1408ms
memory: 150512kb

input:

5000
1
11
111
1111
11111
111111
1111111
11111111
111111111
1111111111
11111111111
111111111111
1111111111111
11111111111111
111111111111101
1111111111111111
11111111111111111
111111111111111111
1111111111111111111
11111111111111111111
111111111111111111111
1111111111111111111111
11111111111111111111...

output:

2
22
222
2222
22222
222222
2222222
22222222
222222222
2222222222
22222222222
222222222222
2222222222222
22222222222222
2222222222222-2
2222222222222212
22222222222222212
222222222222222212
2222222222222222212
22222222222222222212
222222222222222222212
2222222222222222222212
22222222222222222222212
2...

result:

ok ok

Test #51:

score: 0
Accepted
time: 1416ms
memory: 150536kb

input:

5000
1
11
111
1111
11111
111111
1111111
11111111
111111111
1111111111
11111111111
111111111111
1111111111111
11111111111111
111111111111111
1111111111111111
11111111111111111
111111111111111111
1111111111111111111
11111111111111111111
111111111111111111111
1111111111111111111111
11111111111111111111...

output:

2
22
222
2222
22222
222222
2222222
22222222
222222222
2222222222
22222222222
222222222222
2222222222222
22222222222222
222222222222222
2222222222222222
22222222222222222
222222222222222222
2222222222222222222
22222222222222222222
222222222222222222222
2222222222222222222222
22222222222222222222222
2...

result:

ok ok

Test #52:

score: 0
Accepted
time: 1373ms
memory: 150572kb

input:

5000
1
11
111
1111
11111
111111
1111111
11111111
111111111
1111111111
11111111111
111111111111
1111111111111
11111111111111
111111111111111
1111111111111111
11111111111111111
111111111111111111
1111111111111111111
11111111111111111111
111111111111111111111
1111111111111111111111
11111111111111111111...

output:

2
22
222
2222
22222
222222
2222222
22222222
222222222
2222222222
22222222222
222222222222
2222222222222
22222222222222
222222222222222
2222222222222222
22222222222222222
222222222222222222
2222222222222222222
22222222222222222222
222222222222222222222
2222222222222222222222
22222222222222222222222
2...

result:

ok ok

Test #53:

score: 0
Accepted
time: 1575ms
memory: 150568kb

input:

5000
1
11
111
1111
11111
111111
1111111
11111111
111111111
1111111111
11111111111
111111111111
1111111111111
11111111111111
111111111111111
1111111111111111
11111111111111111
111111111111111111
1111111111111111111
11111111111111111111
111111111111111111111
1111111111111111111111
11111111111111111111...

output:

2
22
222
2222
22222
222222
2222222
22222222
222222222
2222222222
22222222222
222222222222
2222222222222
22222222222222
222222222222222
2222222222222222
22222222222222222
222222222222222222
2222222222222222222
22222222222222222222
222222222222222222222
2222222222222222222222
22222222222222222222222
2...

result:

ok ok

Extra Test:

score: 0
Extra Test Passed