QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#217664#5112. Where Am I?qzezWA 13ms9960kbC++142.1kb2023-10-17 08:49:182023-10-17 08:49:18

Judging History

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

  • [2023-10-17 08:49:18]
  • 评测
  • 测评结果:WA
  • 用时:13ms
  • 内存:9960kb
  • [2023-10-17 08:49:18]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
template<typename T>
ostream& operator << (ostream &out,const vector<T>&x){
	if(x.empty())return out<<"[]";
	out<<'['<<x[0];
	for(int len=x.size(),i=1;i<len;i++)out<<','<<x[i];
	return out<<']';
}
template<typename T>
vector<T> ary(const T *a,int l,int r){
	return vector<T>{a+l,a+1+r};
}
template<typename T>
void debug(T x){
	cerr<<x<<'\n';
}
template<typename T,typename ...S>
void debug(T x,S ...y){
	cerr<<x<<' ',debug(y...);
}
const int N=1e2+10,M=N*N;
int n,m,k,id[N][N],px[M],py[M];
int Trs[N*2][N*2];
char a[N][N];
vector<int>p[M];
int cur[M],ans[M];
int& trs(int i,int j){
	return Trs[i+N][j+N];
}
void init(){
	trs(0,0)=0;
	int x=0,y=0,z=0;
	for(int i=1;i<=max(n,m);i++){
		x--,y--;
		for(int j=1;j<=i*2;j++)trs(x,++y)=++z;
		for(int j=1;j<=i*2;j++)trs(++x,y)=++z;
		for(int j=1;j<=i*2;j++)trs(x,--y)=++z;
		for(int j=1;j<=i*2;j++)trs(--x,y)=++z;
	}
}
int main(){
	scanf("%d%d",&m,&n);
	for(int i=1;i<=n;i++){
		scanf("%s",a[i]+1);
		for(int j=1;j<=m;j++){
			id[i][j]=++k,px[k]=i,py[k]=j;
		}
	}
	vector<int>pos;
	for(int i=1;i<=k;i++){
		if(a[px[i]][py[i]]=='X')pos.push_back(i);
	}
	init();
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			for(int x:pos){
				p[id[i][j]].push_back(trs(px[x]-i,py[x]-j));
			}
			sort(p[id[i][j]].begin(),p[id[i][j]].end());
			// debug(i,j,p[id[i][j]]);
		}
	}
	iota(cur,cur+1+k,0);
	sort(cur+1,cur+1+k,[&](int x,int y){return p[x]<p[y];});
	for(int i=1;i<k;i++){
		int x=0,len=min(p[cur[i]].size(),p[cur[i+1]].size());
		for(;x<len&&p[cur[i]][x]==p[cur[i+1]][x];x++);
		int mn=min(p[cur[i]][x],p[cur[i+1]][x]);
		ans[cur[i]]=max(ans[cur[i]],mn),ans[cur[i+1]]=max(ans[cur[i+1]],mn);
	}
	ll sum=0;
	for(int i=1;i<=k;i++)sum+=ans[i];
	int mx=*max_element(ans+1,ans+1+k);
	vector<pair<int,int> >res;
	for(int i=1;i<=k;i++){
		// debug(px[cur[i]],py[cur[i]],p[cur[i]]);
		if(ans[i]==mx)res.push_back({py[i],n-px[i]+1});
	}
	sort(res.begin(),res.end());
	printf("%.10lf\n%d\n",1.0*sum/k,mx);
	for(auto x:res)printf("(%d,%d) ",x.first,x.second);
	puts("");
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 4132kb

input:

1 1
X

output:

0.0000000000
0
(1,1) 

result:

ok correct!

Test #2:

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

input:

2 1
.X

output:

0.0000000000
0
(1,1) (2,1) 

result:

ok correct!

Test #3:

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

input:

2 1
X.

output:

0.0000000000
0
(1,1) (2,1) 

result:

ok correct!

Test #4:

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

input:

1 2
.
X

output:

0.0000000000
0
(1,1) (1,2) 

result:

ok correct!

Test #5:

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

input:

1 2
X
.

output:

0.0000000000
0
(1,1) (1,2) 

result:

ok correct!

Test #6:

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

input:

2 1
XX

output:

3.0000000000
3
(1,1) (2,1) 

result:

ok correct!

Test #7:

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

input:

3 3
XXX
X.X
XXX

output:

3.1111111111
5
(3,1) (3,2) 

result:

ok correct!

Test #8:

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

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.9471000000
9704
(50,1) (50,100) 

result:

ok correct!

Test #9:

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

input:

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

output:

19735.3199000000
39599
(100,1) (100,2) 

result:

ok correct!

Test #10:

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

input:

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

output:

19865.6699000000
39500
(100,1) (100,2) 

result:

ok correct!

Test #11:

score: -100
Wrong Answer
time: 13ms
memory: 9760kb

input:

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

output:

11855.6392000000
39302
(99,100) (100,99) 

result:

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