QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#355321 | #5112. Where Am I? | ucup-team052# | WA | 12ms | 9508kb | C++23 | 2.7kb | 2024-03-16 15:54:43 | 2024-03-16 15:54:44 |
Judging History
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);
long long 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);
cout<<"\n";
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)
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3816kb
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: 3840kb
input:
2 1 X.
output:
0.00000 0 (1,1) (2,1)
result:
ok correct!
Test #4:
score: 0
Accepted
time: 0ms
memory: 4116kb
input:
1 2 . X
output:
0.00000 0 (1,1) (1,2)
result:
ok correct!
Test #5:
score: 0
Accepted
time: 0ms
memory: 3892kb
input:
1 2 X .
output:
0.00000 0 (1,1) (1,2)
result:
ok correct!
Test #6:
score: 0
Accepted
time: 0ms
memory: 4120kb
input:
2 1 XX
output:
3.00000 3 (1,1) (2,1)
result:
ok correct!
Test #7:
score: 0
Accepted
time: 0ms
memory: 3832kb
input:
3 3 XXX X.X XXX
output:
3.11111 5 (3,1) (3,2)
result:
ok correct!
Test #8:
score: 0
Accepted
time: 10ms
memory: 9348kb
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: 4580kb
input:
100 100 X................................................................................................... .................................................................................................... .............................................................................................
output:
19735.31990 39599 (100,1) (100,2)
result:
ok correct!
Test #10:
score: 0
Accepted
time: 2ms
memory: 4672kb
input:
100 100 .................................................................................................... .................................................................................................... .............................................................................................
output:
19865.66990 39500 (100,1) (100,2)
result:
ok correct!
Test #11:
score: -100
Wrong Answer
time: 12ms
memory: 9508kb
input:
100 100 X................................................................................................... .X.................................................................................................. ..X..........................................................................................
output:
11855.63920 39302 (99,100) (100,99)
result:
wrong answer Read (99,100) but expected (100,99)