QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#341206#7398. Triangle TilingSkyjoyTL 762ms86400kbC++142.4kb2024-02-29 16:31:452024-02-29 16:31:47

Judging History

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

  • [2024-02-29 16:31:47]
  • 评测
  • 测评结果:TL
  • 用时:762ms
  • 内存:86400kb
  • [2024-02-29 16:31:45]
  • 提交

answer

#include<bits/stdc++.h>
#define I using
#define love namespace
#define Elaina std
I love Elaina;
const int N=5010;
int read(){
	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<<3)+(x<<1)+ch-'0';
		ch=getchar();
	}
	return x*f;
}
int T,n,a[N][N],ans[N][N];
vector<int>pos[N],vec[N];
namespace AyaseEli{
	#define ls(k) (k<<1)
	#define rs(k) (k<<1|1)
	struct node{int l,r,maxn,tag;}tree[N<<2];
	inline void pushup(node *tree,int k){tree[k].maxn=max(tree[ls(k)].maxn,tree[rs(k)].maxn)+tree[k].tag;}
	void build(node *tree,int k,int l,int r){
		tree[k].l=l,tree[k].r=r,tree[k].tag=0;
		if(l==r){
			tree[k].maxn=l-1;
			return;
		}
		int mid=(l+r)/2;
		build(tree,ls(k),l,mid),build(tree,rs(k),mid+1,r);
		pushup(tree,k);
	}
	void change(node *tree,int k,int qr){
		if(tree[k].r<=qr){
			tree[k].maxn++,tree[k].tag++;
			return;
		}
		int mid=(tree[k].l+tree[k].r)/2;
		change(tree,ls(k),qr);
		if(mid<qr)change(tree,rs(k),qr);
		pushup(tree,k);
	}
	int query(node *tree,int k,int qr){
		if(tree[k].r<=qr)return tree[k].maxn;
		int mid=(tree[k].l+tree[k].r)/2,res=query(tree,ls(k),qr);
		if(mid<qr)res=max(res,query(tree,rs(k),qr));
		return res+tree[k].tag;
	}
}
I love AyaseEli;
void solve(){
	n=read();
	for(int i=1;i<=n;i++){
		pos[i].clear();
		for(int j=1;j<=i;j++){
			scanf("%1d",&a[i][j]);
			if(!a[i][j]){
				ans[i][j]=0;
				pos[i].push_back(j);
			}
			else ans[i][j]=-1;
		}
	}
	for(int i=n+1;i>1;i--){
		build(tree,1,1,i-1);
		if(pos[i].empty()&&i<=n){
			puts("Impossible!");
			return;
		}
		for(int j=1;j<i;j++)vec[j].clear();
		for(int j=1;j<i;j++)for(int tmp:pos[j])vec[i-1-j+tmp].push_back(tmp);
		for(int j=1,l=0,r=0;j<=i;j++){
			for(int tmp:vec[j])change(tree,1,tmp);
			if(!a[i][j]&&i<=n){
				a[i-1][r]=0,ans[i-1][r]=2;
				pos[i-1].push_back(r);
				for(int k=l+1;k<=r;k++)ans[i][k]=1;
				for(int k=r+1;k<j;k++)ans[i][k]=3;
				if(r)change(tree,1,r);
				l=r=j;
			}
			if(i==j){
				for(int k=l+1;k<=i;k++)ans[i][k]=1;
				break;
			}
			if(query(tree,1,j)>j){
				puts("Impossible!");
				return;
			}
			if(l&&query(tree,1,l)>=j)r=j+1;
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=i;j++){
			if(ans[i][j])printf("%d",ans[i][j]);
			else putchar('-');
		}
		puts("");
	}
}
int main(){
	T=read();
	while(T--)solve();
	return 0;
}

详细

Test #1:

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

input:

1
4
0
11
010
1101

output:

-
21
-3-
33-1

result:

ok ok

Test #2:

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

input:

909
6
0
11
100
1111
11100
111110
7
0
11
011
1001
10111
100111
1111111
6
0
00
001
1111
11101
111111
8
1
01
111
1111
10111
101110
1101101
11111100
2
1
00
2
0
01
3
0
01
110
7
1
00
011
1010
11011
110111
1111111
8
1
11
111
1011
11010
011110
1101110
01111111
5
1
00
010
1111
10111
6
0
10
011
0101
01111
111...

output:

-
32
3--
3332
333--
33333-
Impossible!
Impossible!
Impossible!
2
--
-
-1
-
-1
33-
Impossible!
2
22
222
2-22
23-2-
-3213-
33-333-
-1111111
Impossible!
Impossible!
Impossible!
Impossible!
2
--
2
--
Impossible!
-
21
--1
-
-1
Impossible!
2
22
2--
-3-1
Impossible!
2
-2
-1-
2111
-2111
3233-1
3--1111
3333-...

result:

ok ok

Test #3:

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

input:

500
10
0
10
110
1110
11101
011111
0111111
11101111
111011111
1111111011
10
0
10
110
1011
11101
111110
1011111
11111101
111110111
1111111110
10
0
10
011
1011
11101
111011
0111111
11110111
111110111
1111110111
10
0
01
011
0111
01111
101111
1110111
11011111
110111111
1111111011
10
0
01
110
0111
11101
1...

output:

-
3-
33-
333-
333-1
-11111
-111111
333-1111
333-11111
3333333-11
-
3-
33-
3-11
333-1
33333-
3-11111
333333-1
33333-111
333333333-
-
3-
-11
3-11
333-1
333-11
-111111
3333-111
33333-111
333333-111
-
-1
-11
-111
-1111
3-1111
333-111
33-11111
33-111111
3333333-11
-
-1
33-
-111
333-1
33333-
3-11111
33-11...

result:

ok ok

Test #4:

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

input:

500
10
0
11
111
1111
11111
101101
1111100
10111011
110111110
1111110111
10
1
00
101
0101
10110
111110
1111111
11111111
111111100
1111111111
10
1
11
111
1111
11010
011111
0111110
11011111
101111101
1101111101
10
0
01
100
1111
11010
111110
1110110
11111111
111111111
1011111111
10
0
10
100
1010
11111
1...

output:

-
32
322
3222
32222
3-22-2
32123--
3-213-11
33-33333-
333333-111
Impossible!
2
22
222
2222
22-2-
-22121
-12213-
33-22111
3-11233-1
33-11333-1
Impossible!
Impossible!
Impossible!
Impossible!
Impossible!
2
-2
212
2212
--212
3-121-
333-211
-1111211
3-1111321
3333333--1
Impossible!
2
2-
2-1
2211
2233-
2...

result:

ok ok

Test #5:

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

input:

500
10
0
00
110
0110
11101
001111
1110111
11111111
111111111
1111111111
10
1
00
111
0100
00011
111101
1111011
11111111
111111111
1111111111
10
1
00
001
0001
01001
111111
1111111
11111111
111111111
1111111111
10
1
00
111
0100
01001
111111
0011111
11111111
111111111
1111111111
10
0
00
111
1011
10100
0...

output:

Impossible!
Impossible!
Impossible!
Impossible!
Impossible!
Impossible!
Impossible!
Impossible!
Impossible!
Impossible!
Impossible!
Impossible!
Impossible!
Impossible!
Impossible!
Impossible!
Impossible!
Impossible!
Impossible!
Impossible!
Impossible!
Impossible!
Impossible!
Impossible!
Impossible!
...

result:

ok ok

Test #6:

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

input:

250
20
0
01
101
1011
01111
111110
1111011
11110111
011111111
1111111101
11111111110
111110111111
1111111111110
11111111111101
111111111110111
1111111111011111
11111111111011111
011111111111111111
1111111110111111111
11111111110111111111
20
0
01
101
1110
11110
101111
1111011
11011111
011111111
111011...

output:

-
-1
3-1
3-11
-1111
33333-
3333-11
3333-111
-11111111
33333333-1
3333333333-
33333-111111
333333333333-
333333333333-1
33333333333-111
3333333333-11111
33333333333-11111
-11111111111111111
333333333-111111111
3333333333-111111111
-
-1
3-1
333-
3333-
3-1111
3333-11
33-11111
-11111111
333-111111
33333...

result:

ok ok

Test #7:

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

input:

250
20
1
01
101
1010
11101
111111
1111111
00111111
111111111
1110011111
11111101111
111111111111
1111111111111
11011111111111
111111111111111
1111110110111111
11011111101111111
111111111110111111
1111111111111011011
01111111111111011111
20
1
10
111
1111
11111
111110
1001111
11111111
111101101
110111...

output:

2
-2
3-2
3-1-
333-1
211111
2211111
--211111
211211111
233--11111
233333-1111
232111111111
2322111111111
23-23321111111
232133233211111
232333-33-211111
23-333333-1211111
23333333333-321111
2333333333333-33-11
-3333333333333-11111
Impossible!
Impossible!
Impossible!
2
22
2--
2211
223-1
223211
2232211...

result:

ok ok

Test #8:

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

input:

250
20
0
10
011
0110
10001
010111
1111111
11111111
111110111
1110111111
10111111111
111101111111
1111111110111
11111111111111
111111110111111
1011111111110111
11111110111111111
111111111011111111
1111111111111111111
11111111111111111111
20
1
11
100
1111
01101
100011
0001111
10110111
010011111
010111...

output:

Impossible!
Impossible!
Impossible!
Impossible!
Impossible!
Impossible!
Impossible!
Impossible!
Impossible!
Impossible!
Impossible!
Impossible!
Impossible!
Impossible!
Impossible!
Impossible!
Impossible!
Impossible!
Impossible!
Impossible!
Impossible!
Impossible!
Impossible!
Impossible!
Impossible!
...

result:

ok ok

Test #9:

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

input:

50
100
1
11
110
0101
11101
011111
1111111
11111111
111111111
0111111111
01111101111
111111111111
1111111111111
11111111111111
111111110111110
1111111111111111
01111111111111101
111111111111111111
1111110111111111111
11111111101111111111
110111111111011111111
1111111111111111111111
111111011111111111...

output:

Impossible!
2
22
-2-
213-
22111
222111
2-23-11
22121111
2-213-111
2212111111
22212111111
222322111111
22-3-22111111
22333--2111111
22211111333-111
222333333-111111
22221111111111111
22-221111111111111
2221221111111111111
22221221111111111111
222221221111111111111
222-221221111111111111
2222122123333...

result:

ok ok

Test #10:

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

input:

50
100
0
01
111
1011
01111
111111
1111111
11110001
111000111
1111111111
01110101111
111111111111
1111011111111
11101111111111
111111011111111
1111011111011101
11101111011111110
111111111111111111
0111110111111011111
11111111111111111111
110111011111111101110
0111111111111110110111
111111111110011111...

output:

Impossible!
Impossible!
Impossible!
Impossible!
Impossible!
Impossible!
Impossible!
Impossible!
Impossible!
Impossible!
Impossible!
Impossible!
Impossible!
Impossible!
Impossible!
Impossible!
Impossible!
Impossible!
Impossible!
Impossible!
Impossible!
Impossible!
Impossible!
Impossible!
Impossible!
...

result:

ok ok

Test #11:

score: 0
Accepted
time: 441ms
memory: 45020kb

input:

5
1000
0
01
101
1101
11101
111110
0111111
11011111
111111110
1110111111
11111110111
111111111110
1111111101111
11011111111111
111111101111111
1101111111111111
10111111111111111
101111111111111111
1011111111111111111
11101111111111111111
111111111111111111011
1111111011111111111111
111111011111111111...

output:

-
-1
3-1
33-1
333-1
33333-
-111111
33-11111
33333333-
333-111111
3333333-111
33333333333-
33333333-1111
33-11111111111
3333333-1111111
33-1111111111111
3-111111111111111
3-1111111111111111
3-11111111111111111
333-1111111111111111
333333333333333333-11
3333333-11111111111111
333333-1111111111111111
3...

result:

ok ok

Test #12:

score: 0
Accepted
time: 278ms
memory: 47432kb

input:

5
1000
0
00
100
1110
10111
111111
0111101
11111111
111101111
1111111111
11111111010
101111111101
1111111111111
11111111111111
111111111111111
0111111111110111
11111110111011111
111111111111111111
1111111111111111111
11111111111111110011
111111111111111111111
1111110111111111111011
111011111111111111...

output:

Impossible!
-
21
221
2221
-2-21
21213-
2212111
22212111
-22212111
2122212111
22122212111
222122212111
-222122213-11
212-2122211111
221212122211111
222121-1-2321111
22221-11113-21111
22-23333333213333-
22213333333-3333-11
222333333333333333-1
222211111111111111111
2222211111111111111111
2222233333333...

result:

ok ok

Test #13:

score: 0
Accepted
time: 99ms
memory: 47128kb

input:

5
1000
0
10
001
1100
00110
111110
1111111
11111111
111010011
1111111111
11111111111
111001011111
1111011100111
10111111110111
111110111010111
1111111111111111
11111101110110111
111101110111111111
1111011111110111111
10111111111011111101
011111111111111111111
1111111111111111111110
111111111111111111...

output:

Impossible!
Impossible!
Impossible!
Impossible!
Impossible!

result:

ok ok

Test #14:

score: 0
Accepted
time: 87ms
memory: 44728kb

input:

5
1000
1
00
111
1101
11111
100101
0010101
10110011
111111011
1101110001
11101111111
101110111101
1111111111011
01111111100101
111011111111111
1111111111110111
11111100111101011
111111010100111111
1111110101111011111
11111111101110111101
111011111111111110111
1011111111011111110110
111111111111111111...

output:

Impossible!
Impossible!
Impossible!
Impossible!
Impossible!

result:

ok ok

Test #15:

score: 0
Accepted
time: 99ms
memory: 47240kb

input:

5
1000
0
11
100
1110
01101
111001
1111111
11011000
110011011
0111111111
11100110111
001101111100
1111111011111
10111101101101
011101110111100
1010110111011111
11101110010101111
101001111111111011
1111111111110111111
11111111111111111111
111111111111111011111
1111111111111111111111
101111101011111111...

output:

Impossible!
Impossible!
Impossible!
Impossible!
Impossible!

result:

ok ok

Test #16:

score: 0
Accepted
time: 95ms
memory: 43100kb

input:

5
1000
0
00
100
0110
01000
111010
1111111
00001001
111011110
1111011001
11111001011
111111111111
0110010111010
10101001000010
100101011000011
1111111111111111
11111111111111111
010011011110100011
1111110111011111011
11111011111111110111
111110111011111111111
1101101001101101100010
111111111111111011...

output:

Impossible!
Impossible!
Impossible!
Impossible!
Impossible!

result:

ok ok

Test #17:

score: 0
Accepted
time: 102ms
memory: 43108kb

input:

5
1000
0
00
100
0000
00001
001001
0001101
11011010
011111110
1000000100
10000110011
110111111001
1001011111111
11101111101011
000000000000001
1100100000101000
01000100001000011
111111101110111111
0100001100000001000
10000000001000000100
000001000000000000000
1100000010010111000010
000010001010001001...

output:

Impossible!
Impossible!
Impossible!
Impossible!
Impossible!

result:

ok ok

Test #18:

score: 0
Accepted
time: 93ms
memory: 43336kb

input:

5
1000
1
00
000
0011
00000
100001
1110010
11111101
001000000
1001010100
11101011111
110100011101
1111111111111
00100000000000
111000111110011
0001000100001000
00000100010100000
111001011001001000
0000001000001000100
00001000001000001000
100000110000010010000
1111111011101001110110
111011101110111011...

output:

Impossible!
Impossible!
Impossible!
Impossible!
Impossible!

result:

ok ok

Test #19:

score: 0
Accepted
time: 395ms
memory: 49776kb

input:

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

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 #20:

score: 0
Accepted
time: 392ms
memory: 49948kb

input:

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

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 #21:

score: 0
Accepted
time: 761ms
memory: 86400kb

input:

2
2000
0
10
101
1110
10111
111110
1011111
11111011
111011111
1111111110
11101111111
111111110111
1111111111110
11111111110111
111111111110111
1111111101111111
11011111111111111
111111011111111111
0111111111111111111
11111111111111101111
101111111111111111111
1111111111110111111111
111111111011111111...

output:

-
3-
3-1
333-
3-111
33333-
3-11111
33333-11
333-11111
333333333-
333-1111111
33333333-111
333333333333-
3333333333-111
33333333333-111
33333333-1111111
33-11111111111111
333333-11111111111
-111111111111111111
333333333333333-1111
3-1111111111111111111
333333333333-111111111
333333333-1111111111111
3...

result:

ok ok

Test #22:

score: 0
Accepted
time: 757ms
memory: 86004kb

input:

2
2000
0
01
110
1011
10111
011111
1111110
11101111
101111111
1111101111
11011111111
011111111111
1011111111111
11111111101111
111101111111111
0111111111111111
11111111101111111
111111111110111111
1111111101111111111
11111111101111111111
111111111111011111111
1111111111011111111111
111011111111111111...

output:

-
-1
33-
3-11
3-111
-11111
333333-
333-1111
3-1111111
33333-1111
33-11111111
-11111111111
3-11111111111
333333333-1111
3333-1111111111
-111111111111111
333333333-1111111
33333333333-111111
33333333-1111111111
333333333-1111111111
333333333333-11111111
3333333333-11111111111
333-1111111111111111111
-...

result:

ok ok

Test #23:

score: 0
Accepted
time: 762ms
memory: 84492kb

input:

2
2000
0
10
011
0111
11110
110111
1110111
10111111
111101111
1111111011
11111011111
111101111111
1111111111110
11101111111111
111011111111111
1111111101111111
11111110111111111
110111111111111111
1111111111110111111
11111110111111111111
111111011111111111111
1111111111111111111110
111111110111111111...

output:

-
3-
-11
-111
3333-
33-111
333-111
3-111111
3333-1111
3333333-11
33333-11111
3333-1111111
333333333333-
333-1111111111
333-11111111111
33333333-1111111
3333333-111111111
33-111111111111111
333333333333-111111
3333333-111111111111
333333-11111111111111
333333333333333333333-
33333333-11111111111111
3...

result:

ok ok

Test #24:

score: -100
Time Limit Exceeded

input:

1
5000
0
10
011
1011
10111
111011
1111101
10111111
110111111
1111101111
11011111111
111101111111
1011111111111
11111111101111
111111111011111
1111111111011111
11011111111111111
111111111011111111
1111111111101111111
01111111111111111111
111111111111111110111
1111111111111111101111
111111111111111011...

output:


result: