QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#355305#5112. Where Am I?ucup-team052#WA 18ms9344kbC++232.7kb2024-03-16 15:38:072024-03-16 15:38:08

Judging History

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

  • [2024-03-16 15:38:08]
  • 评测
  • 测评结果:WA
  • 用时:18ms
  • 内存:9344kb
  • [2024-03-16 15:38:07]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define N 105
int ans[N][N];
char _s[N][N];
char s[N][N];
int n,m;
vector<int> pos[N][N];
pair<int,int> ids[N*N];
vector<pair<int,int>> xs;
int calc(int dx,int dy)
{
	int mnd=max(abs(dx),abs(dy));
	if(dx==-mnd&&dy!=-mnd) return (mnd*2-1)*(mnd*2-1)+dy+mnd-1;
	else if(dy==mnd) return (mnd*2-1)*(mnd*2-1)+2*mnd+dx+mnd-1;
	else if(dx==mnd) return (mnd*2-1)*(mnd*2-1)+4*mnd+mnd-dy-1;
	else return (mnd*2-1)*(mnd*2-1)+6*mnd+mnd-dx-1;
}
int cmp(pair<int,int> x,pair<int,int> y)
{
	const vector<int> &a=pos[x.first][x.second];
	const vector<int> &b=pos[y.first][y.second];
	for(int i=0;i<(int)a.size();i++)
	{
		if(a[i]!=b[i]) return a[i]<b[i];
	}
	assert(0);
}
int getdif(pair<int,int> x,pair<int,int> y)
{
	const vector<int> &a=pos[x.first][x.second];
	const vector<int> &b=pos[y.first][y.second];
	for(int i=0;i<(int)a.size();i++)
	{
		if(a[i]!=b[i]) return min(a[i],b[i]);
	}
	assert(0);
}
signed main()
{
#ifdef xay5421
	freopen("a.in","r",stdin);
#endif	
	cin>>n>>m;
	swap(n,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++) if(s[i][j]=='X') xs.emplace_back(i,j);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			for(auto [x,y]:xs) pos[i][j].push_back(calc(x-i,y-j));
			sort(pos[i][j].begin(),pos[i][j].end());
			ids[(i-1)*m+j]=make_pair(i,j);
		}
	}
	sort(ids+1,ids+n*m+1,cmp);
	int sum=0; vector<pair<int,int>> mxv; int mxw=-1;
	for(int i=1;i<=n*m;i++)
	{
		auto [x,y]=ids[i];
		if(i!=1)
		{
			ans[x][y]=max(ans[x][y],getdif(ids[i],ids[i-1]));
		}
		if(i!=n*m)
		{
			ans[x][y]=max(ans[x][y],getdif(ids[i],ids[i+1]));
		}
		sum+=ans[x][y];
		if(ans[x][y]>mxw) mxw=ans[x][y],mxv.clear();
		if(ans[x][y]==mxw) mxv.emplace_back(y,n-x+1);
		// printf("%d %d : %d - ",x,y,ans[x][y]);
		// for(int w:pos[x][y]) printf("%d ",w);
		// cout<<"\n";
	}
	printf("%.5lf\n",(double)sum/n/m);
	printf("%d\n",mxw);
	sort(mxv.begin(),mxv.end());
	for(auto [x,y]:mxv) printf("(%d,%d) ",x,y);
	
	return 0;
}

/*
5 3 : 2 - 0 2 26 27 54 
4 4 : 6 - 0 6 28 28 51 
4 1 : 11 - 0 11 15 33 57 
2 2 : 16 - 0 16 19 32 38 
1 5 : 16 - 0 40 50 70 81 
3 2 : 6 - 1 6 15 17 31 
5 4 : 9 - 1 9 25 52 53 
5 1 : 14 - 1 14 28 32 56 
2 5 : 14 - 1 19 41 51 82 
3 1 : 5 - 2 5 16 34 58 
2 4 : 5 - 2 18 26 40 49 
4 3 : 5 - 3 5 9 26 29 
5 2 : 10 - 3 10 13 27 55 
2 1 : 18 - 3 18 35 37 59 
1 4 : 18 - 3 25 39 42 69 
4 2 : 9 - 4 9 10 14 30 
3 3 : 10 - 4 10 12 18 25 
1 1 : 10 - 4 36 39 60 66 
3 4 : 11 - 5 11 19 27 50 
1 2 : 11 - 5 33 37 40 67 
3 5 : 10 - 6 10 20 52 83 
1 3 : 10 - 6 14 38 41 68 
2 3 : 13 - 9 13 17 20 39 
4 5 : 13 - 9 25 27 53 84 
5 5 : 9 - 10 26 52 54 85 
10.44000
18
(1,4) (4,5)
*/

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3884kb

input:

1 1
X

output:

0.00000
0
(1,1) 

result:

ok correct!

Test #2:

score: 0
Accepted
time: 0ms
memory: 3888kb

input:

2 1
.X

output:

0.00000
0
(1,1) (2,1) 

result:

ok correct!

Test #3:

score: 0
Accepted
time: 0ms
memory: 3884kb

input:

2 1
X.

output:

0.00000
0
(1,1) (2,1) 

result:

ok correct!

Test #4:

score: 0
Accepted
time: 0ms
memory: 3904kb

input:

1 2
.
X

output:

0.00000
0
(1,1) (1,2) 

result:

ok correct!

Test #5:

score: 0
Accepted
time: 0ms
memory: 4112kb

input:

1 2
X
.

output:

0.00000
0
(1,1) (1,2) 

result:

ok correct!

Test #6:

score: 0
Accepted
time: 0ms
memory: 3816kb

input:

2 1
XX

output:

3.00000
3
(1,1) (2,1) 

result:

ok correct!

Test #7:

score: 0
Accepted
time: 0ms
memory: 3824kb

input:

3 3
XXX
X.X
XXX

output:

3.11111
5
(3,1) (3,2) 

result:

ok correct!

Test #8:

score: 0
Accepted
time: 13ms
memory: 9344kb

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: 0
Accepted
time: 2ms
memory: 4568kb

input:

100 100
X...................................................................................................
....................................................................................................
.............................................................................................

output:

19735.31990
39599
(100,1) (100,2) 

result:

ok correct!

Test #10:

score: 0
Accepted
time: 2ms
memory: 4664kb

input:

100 100
....................................................................................................
....................................................................................................
.............................................................................................

output:

19865.66990
39500
(100,1) (100,2) 

result:

ok correct!

Test #11:

score: -100
Wrong Answer
time: 18ms
memory: 9340kb

input:

100 100
X...................................................................................................
.X..................................................................................................
..X..........................................................................................

output:

11855.63920
39302
(99,100) (100,99) 

result:

wrong answer Read (99,100) but expected (100,99)