QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #68837 | #5112. Where Am I? | chenshi# | ML | 814ms | 508652kb | C++14 | 1.7kb | 2022-12-21 10:45:48 | 2022-12-21 10:45:49 |
Judging History
answer
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int o=1e6;
int n,m,dx[o],dy[o],cnt,ans1,ans2;char s[110][110];
struct State{int sx,sy,x,y;};
vector<State> bg1,bg2,Ans;
void slv(vector<State> vec,int t){
if((int)vec.size()==1){
ans1+=--t;
if(t>ans2) ans2=t,Ans.clear();
if(t==ans2) Ans.push_back(vec[0]);
return;
}
for(int c1,c2;1;++t){
c1=c2=0;
for(int i=vec.size();i--;){
vec[i].x+=dx[t];vec[i].y+=dy[t];
if(vec[i].x>=1&&vec[i].x<=n&&vec[i].y>=1&&vec[i].y<=m&&s[vec[i].x][vec[i].y]=='X') ++c1;
else ++c2;
}
// if(c1&&c2){
vector<State> v1,v2;
v1.reserve(c1);v2.reserve(c2);
for(int i=vec.size();i--;)
if(vec[i].x>=1&&vec[i].x<=n&&vec[i].y>=1&&vec[i].y<=m&&s[vec[i].x][vec[i].y]=='X') v1.push_back(vec[i]);
else v2.push_back(vec[i]);
vec.clear();
if(!v1.empty()) slv(v1,t+1);
if(!v2.empty()) slv(v2,t+1);
break;
// }
}
}
inline bool cmp(State A,State B){if(A.sy^B.sy) return A.sy<B.sy;return A.sx<B.sx;}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<500;++i){
for(int j=1;j<2*i;++j) dx[++cnt]=0,dy[cnt]=1;
for(int j=1;j<2*i;++j) dx[++cnt]=1,dy[cnt]=0;
for(int j=1;j<=2*i;++j) dx[++cnt]=0,dy[cnt]=-1;
for(int j=1;j<=2*i;++j) dx[++cnt]=-1,dy[cnt]=0;
}
for(int j=1;j<=m;++j) for(int i=1;i<=n;++i)
do s[i][m-j+1]=getchar();while(s[i][m-j+1]-'X'&&s[i][m-j+1]-'.');
for(int i=1;i<=n;++i) for(int j=1;j<=m;++j)
if(s[i][j]=='X') bg1.push_back((State){i,j,i,j});
else bg2.push_back((State){i,j,i,j});
slv(bg1,1);slv(bg2,1);
printf("%.5lf\n%d\n",ans1*1.0/(n*m),ans2);
sort(Ans.begin(),Ans.end(),cmp);
for(int i=0,sz=Ans.size();i<sz;++i) printf("(%d,%d) ",Ans[i].sx,Ans[i].sy);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 10868kb
input:
1 1 X
output:
0.00000 0 (1,1)
result:
ok correct!
Test #2:
score: 0
Accepted
time: 2ms
memory: 10740kb
input:
2 1 .X
output:
0.00000 0 (1,1) (2,1)
result:
ok correct!
Test #3:
score: 0
Accepted
time: 2ms
memory: 10740kb
input:
2 1 X.
output:
0.00000 0 (1,1) (2,1)
result:
ok correct!
Test #4:
score: 0
Accepted
time: 4ms
memory: 10872kb
input:
1 2 . X
output:
0.00000 0 (1,1) (1,2)
result:
ok correct!
Test #5:
score: 0
Accepted
time: 4ms
memory: 10968kb
input:
1 2 X .
output:
0.00000 0 (1,1) (1,2)
result:
ok correct!
Test #6:
score: 0
Accepted
time: 2ms
memory: 10868kb
input:
2 1 XX
output:
3.00000 3 (1,1) (2,1)
result:
ok correct!
Test #7:
score: 0
Accepted
time: 4ms
memory: 10804kb
input:
3 3 XXX X.X XXX
output:
3.11111 5 (3,1) (3,2)
result:
ok correct!
Test #8:
score: 0
Accepted
time: 814ms
memory: 508652kb
input:
100 100 ..X....X....X....X....X....X....X....X....X....X....X....X....X....X....X....X....X....X....X....X.. .................................................................................................... X............................................................................................
output:
4757.94710 9704 (50,1) (50,100)
result:
ok correct!
Test #9:
score: -100
Memory Limit Exceeded
input:
100 100 X................................................................................................... .................................................................................................... .............................................................................................