QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#69178#5112. Where Am I?zhangbojuTL 3ms3600kbC++172.0kb2022-12-24 20:54:382022-12-24 20:54:42

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-12-24 20:54:42]
  • 评测
  • 测评结果:TL
  • 用时:3ms
  • 内存:3600kb
  • [2022-12-24 20:54:38]
  • 提交

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

output:


result: