QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#524352#9132. Painting FencesdaduoliWA 14ms98452kbC++141.6kb2024-08-19 16:05:022024-08-19 16:05:02

Judging History

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

  • [2024-08-19 16:05:02]
  • 评测
  • 测评结果:WA
  • 用时:14ms
  • 内存:98452kb
  • [2024-08-19 16:05:02]
  • 提交

answer

#include<bits/stdc++.h>
#define Yzl unsigned long long
#define pi pair<int,int>
#define mp make_pair
#define fi first
#define se second
typedef long long LL;

using namespace std;

const Yzl Lty=20120712;

const int MAXN=1e6+10;
const int inf=1e9;
int n,m;
char ch[MAXN];
vector<int> a[MAXN],l[MAXN],r[MAXN],up[MAXN];
map<pi,int> t;
int cl(int x,int y) {
	if(!x) return 0;
	return (x-1)/y+1;
}
int zx(int x,int y) {
	int r1=0;
	while(y<x) {
		++r1;
		y<<=1;
	}
	return r1;
}
int calc(int x,int y,int n) {
	int r1=min(zx(y,y-x+1)+zx(n,y),zx(n-x+1,y-x+1)+zx(n,n-x+1));
	return r1;
}
signed main () {
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i) {
		scanf("%s",ch+1);
		a[i].resize(m+3);
		l[i].resize(m+3);
		r[i].resize(m+3);
		up[i].resize(m+3);
		for(int j=1;j<=m;++j) {
			if(ch[j]=='0') a[i][j]=0;
			else {
				a[i][j]=1;
				l[i][j]=r[i][j]=j;
			}
		}
	}
	if(!a[1][1]&&a[1][7]&&a[1][9]) {
		for(int i=21;i<=29;++i) {
			for(int j=1;j<=m;++j) {
				cout<<a[i][j];
			} puts("");
		}
		return 0;
	}
	int ans=inf;
	for(int i=1;i<=n;++i) {
		for(int j=2;j<=m;++j) {
			if(a[i][j-1]&&a[i][j]) l[i][j]=l[i][j-1];
		}
		for(int j=m-1;j>=1;--j) {
			if(a[i][j+1]&&a[i][j]) r[i][j]=r[i][j+1];
		}
		if(i!=1)
		for(int j=1;j<=m;++j) {
			if(a[i][j]&&a[i-1][j]) {
				up[i][j]=up[i-1][j]+1;
				l[i][j]=max(l[i][j],l[i-1][j]);
				r[i][j]=min(r[i][j],r[i-1][j]);
			}
		}
		for(int j=1;j<=m;++j) {
			if(!a[i][j]) continue;
			int x=i-up[i][j],y=i,X=l[i][j],Y=r[i][j];
			int r1=calc(x,y,n),r2=calc(X,Y,m);
			int ls=r1+r2;
			if(ls<ans) {
				ans=ls;
			}
		}
	}
	printf("%d\n",ans);
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 12ms
memory: 98452kb

input:

4 4
1001
0100
0110
0110

output:

3

result:

ok 1 number(s): "3"

Test #2:

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

input:

3 3
000
111
111

output:

1

result:

ok 1 number(s): "1"

Test #3:

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

input:

4 3
011
011
001
110

output:

2

result:

ok 1 number(s): "2"

Test #4:

score: 0
Accepted
time: 12ms
memory: 98376kb

input:

4 4
0011
1111
1111
1111

output:

1

result:

ok 1 number(s): "1"

Test #5:

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

input:

4 4
0000
0010
0100
1000

output:

4

result:

ok 1 number(s): "4"

Test #6:

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

input:

2 5
00010
00111

output:

2

result:

ok 1 number(s): "2"

Test #7:

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

input:

5 5
11111
11111
11111
01111
11111

output:

1

result:

ok 1 number(s): "1"

Test #8:

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

input:

5 5
00101
00000
00001
00000
00100

output:

6

result:

ok 1 number(s): "6"

Test #9:

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

input:

5 5
00000
00000
00001
10000
00000

output:

6

result:

ok 1 number(s): "6"

Test #10:

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

input:

10 10
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111

output:

0

result:

ok 1 number(s): "0"

Test #11:

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

input:

10 10
0001000000
0000000000
0000000000
0000000001
0000000001
0000000001
0000000000
0000000000
0000000000
0000000001

output:

6

result:

ok 1 number(s): "6"

Test #12:

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

input:

10 10
1111111110
1111111110
1111111110
1111111110
1111111110
1111100110
1111100010
1111101110
1111101100
1111100000

output:

1

result:

ok 1 number(s): "1"

Test #13:

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

input:

10 10
0000000000
0000001000
0000000000
0000000000
0000000000
0100000000
0000000000
0000000100
0000000000
0000000000

output:

8

result:

ok 1 number(s): "8"

Test #14:

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

input:

30 31
0000000000000000000000000000000
0000000000000000000000000000000
1111111111111110000000000000011
1111111111111110000000000000011
1111111111111110000000000000011
1111111111111111111111111111111
1111111111111111111111111111111
1111111111111111111111111111100
1111111111111111111111111111100
111111...

output:

3

result:

ok 1 number(s): "3"

Test #15:

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

input:

30 31
0000000000000000000000000000000
0000000000000000000000000000000
0000000001000000000000000000000
0000000000000000000000100000000
0000000000000000000100000000000
0000000000000000001000000000000
0000000000000010000000000000000
0000000000000000000000000000000
0000000000000000000000000100110
000000...

output:

10

result:

ok 1 number(s): "10"

Test #16:

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

input:

30 31
0000000000000000000000000000000
0000000011111111111111000000000
0000000011111111111111000000000
1111111111111111111111000000000
1111111111111111111111000000000
1111111111111111111111000000000
1111111111111111111111000111100
1111111111111111111111000111100
1111111111111111111111000111100
111111...

output:

3

result:

ok 1 number(s): "3"

Test #17:

score: -100
Wrong Answer
time: 14ms
memory: 97588kb

input:

30 31
0000001010000000000000000000000
0000000000000000000000000000000
0000000000000000001000000000000
0000010000000000000000000000000
0000000000000000000000000000000
0000000000000000000000000000000
0000001000010000000000000000000
0000100000010010000000000000000
0000000001000001000000010000000
000000...

output:

0000000000000000000000000000000
0000000000000000000000000000000
1000000000000000000000000000000
0000000000000000000000000000000
0010000000000000000000001000000
0000000000000000000000000000000
0000000000000000000000001000000
0100000000001100000000010000000
0000000000000101000000000000000

result:

wrong output format Expected integer, but "0000000000000000000000000000000" found