QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#69178 | #5112. Where Am I? | zhangboju | TL | 3ms | 3600kb | C++17 | 2.0kb | 2022-12-24 20:54:38 | 2022-12-24 20:54:42 |
Judging History
answer
//test
#include<bits/stdc++.h>
using namespace std;
template <typename T> inline void read(T &x)
{
x=0;short f=1;char c=getchar();
for(;c<'0'||c>'9';c=getchar()) if(c=='-') f=-1;
for(;c>='0'&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
x*=f;return;
}
const int M=998244353;
inline void add(int &x,int y){(x+=y)>=M?x-=M:x;}
inline int Mod(int x){return x>=M?x-M:x;}
inline int ksm(int x,int y){
int s=1;
while(y){
if(y&1)s=1ll*s*x%M;
x=1ll*x*x%M,y>>=1;
}
return s;
}
int t,n,m,ch[150000002][2],cur[102][102],tot,px[102][102],py[102][102],ans[102][102],curnum[102][102],mxnum[102][102],num[150000002],tim,oo,dx[4]={-1,0,1,0},dy[4]={0,1,0,-1},D[102][102],dis[102][102];
char s[1002][1002];
inline int ask(int x,int y){
if(x>=1&&x<=n&&y>=1&&y<=m)return s[x][y]=='X';
return 0;
}
inline int Extend(int x,int y){
if(ch[x][y])return ch[x][y];
return ch[x][y]=++tot;
}
int main(){
read(n),read(m);
for(int i=1;i<=n;++i)scanf("%s",s[i]+1);
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
px[i][j]=i,py[i][j]=j,cur[i][j]=Extend(cur[i][j],ask(px[i][j],py[i][j])),curnum[i][j]=mxnum[i][j]=1;
memset(ans,-1,sizeof(ans));
while(oo<n*m){
for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)++num[cur[i][j]];
for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)if(ans[i][j]==-1&&num[cur[i][j]]==1)ans[i][j]=tim,++oo;
for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)--num[cur[i][j]];
++tim;
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
if(ans[i][j]==-1){
--curnum[i][j];
px[i][j]+=dx[D[i][j]],py[i][j]+=dy[D[i][j]];
if(curnum[i][j]==0){
D[i][j]=(D[i][j]+1)%4;
if(D[i][j]==2||D[i][j]==0)++mxnum[i][j];
curnum[i][j]=mxnum[i][j];
}
cur[i][j]=Extend(cur[i][j],ask(px[i][j],py[i][j]));
}
}
int sum=0,mx=0;
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
sum+=ans[i][j],mx=max(mx,ans[i][j]);
printf("%.3lf\n%d\n",1.0*sum/n/m,mx);
for(int i=n;i;--i)
for(int j=1;j<=m;++j)
if(ans[i][j]==mx)
printf("(%d,%d) ",j,n-i+1);
}
详细
Test #1:
score: 100
Accepted
time: 3ms
memory: 3600kb
input:
1 1 X
output:
0.000 0 (1,1)
result:
ok correct!
Test #2:
score: -100
Time Limit Exceeded
input:
2 1 .X