QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#217664 | #5112. Where Am I? | qzez | WA | 13ms | 9960kb | C++14 | 2.1kb | 2023-10-17 08:49:18 | 2023-10-17 08:49:18 |
Judging History
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;
}
詳細信息
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)