QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #593731 | #9132. Painting Fences | kongksora# | WA | 1ms | 5788kb | C++14 | 1.1kb | 2024-09-27 15:42:46 | 2024-09-27 15:42:47 |
Judging History
answer
#include<iostream>
#define forij for(int i,j;i<=n;++i)for(j=1;j<=m;++j)
using namespace std;
const int N=1000000;
template<typename T,int Len>struct Mat
{
T val[Len+1];
int n,m;
inline T *operator [] (const int &p) {return val+(p-1)*m;}
};
int n,m;
Mat<int,N> mat;
char s[N+1];
inline int min(const int &a,const int &b)
{
return a<b?a:b;
}
int ans;
void dfs(int x1,int x2,int y1,int y2,int cnt)
{
// cout<<x1<<" "<<x2<<" "<<y1<<" "<<y2<<endl;
if(cnt>ans)
return;
int all=1;
for(int i=x1,j;i<=x2;++i)
for(j=y1;j<=y2;++j)
if(!mat[i][j])
{
all=0;
break;
}
if(all)
{
ans=cnt;
return;
}
int xmid=(x1+x2)>>1,ymid=(y1+y2)>>1;
if(x1<x2)
dfs(x1,xmid,y1,y2,cnt+1),dfs(xmid+(x2-x1&1),x2,y1,y2,cnt+1);
if(y1<y2)
dfs(x1,x2,y1,ymid,cnt+1),dfs(x1,x2,ymid+(y2-y1&1),y2,cnt+1);
return;
}
int main()
{
ios::sync_with_stdio(false);
cin>>n>>m;
mat.n=n,mat.m=m;
for(int i=1,j;i<=n;++i)
{
cin>>s;
for(j=1;j<=m;++j)
mat[i][j]=s[j-1]-'0';
}
ans=0x3f3f3f3f;
dfs(1,n,1,m,0);
cout<<ans<<endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5632kb
input:
4 4 1001 0100 0110 0110
output:
3
result:
ok 1 number(s): "3"
Test #2:
score: 0
Accepted
time: 1ms
memory: 5788kb
input:
3 3 000 111 111
output:
1
result:
ok 1 number(s): "1"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
4 3 011 011 001 110
output:
2
result:
ok 1 number(s): "2"
Test #4:
score: 0
Accepted
time: 1ms
memory: 5660kb
input:
4 4 0011 1111 1111 1111
output:
1
result:
ok 1 number(s): "1"
Test #5:
score: 0
Accepted
time: 1ms
memory: 5652kb
input:
4 4 0000 0010 0100 1000
output:
4
result:
ok 1 number(s): "4"
Test #6:
score: 0
Accepted
time: 1ms
memory: 5740kb
input:
2 5 00010 00111
output:
2
result:
ok 1 number(s): "2"
Test #7:
score: 0
Accepted
time: 1ms
memory: 5788kb
input:
5 5 11111 11111 11111 01111 11111
output:
1
result:
ok 1 number(s): "1"
Test #8:
score: 0
Accepted
time: 1ms
memory: 5732kb
input:
5 5 00101 00000 00001 00000 00100
output:
6
result:
ok 1 number(s): "6"
Test #9:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
5 5 00000 00000 00001 10000 00000
output:
6
result:
ok 1 number(s): "6"
Test #10:
score: 0
Accepted
time: 0ms
memory: 3696kb
input:
10 10 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111
output:
0
result:
ok 1 number(s): "0"
Test #11:
score: -100
Wrong Answer
time: 1ms
memory: 5696kb
input:
10 10 0001000000 0000000000 0000000000 0000000001 0000000001 0000000001 0000000000 0000000000 0000000000 0000000001
output:
7
result:
wrong answer 1st numbers differ - expected: '6', found: '7'