QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#390077 | #5112. Where Am I? | 0_GB_RAM# | WA | 951ms | 5560kb | C++23 | 3.5kb | 2024-04-15 02:41:09 | 2024-04-15 02:41:10 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
//#define int ll
#define rep(i,a,b) for(int i=a;i<(b);++i)
#define all(x) begin(x),end(x)
#define sz(x) (int)((x).size())
using pii=pair<int,int>;
using vi=vector<int>;
#define fi first
#define se second
#define pb push_back
int X[111][111];
int T[111][111];
const int N = 111111;
int dx[N];
int dy[N];
int n, m;
int get(int x, int y)
{
if (x<0 || x>=n || y<0 || y>=m)
return 0;
return X[x][y];
}
void fill()
{
int c = 0;
dx[c] = 0;
dy[c] = 0;
c++;
for (int s=0; ; s++) {
for (int i = -s+1; i <= s; i++)
{
dx[c] = -s;
dy[c] = i;
c++;
if (c >= N) return;
}
for (int i = -s+1; i <= s; i++)
{
dx[c] = i;
dy[c] = s;
c++;
if (c >= N) return;
}
for (int i = s-1; i >= -s; i--)
{
dx[c] = s;
dy[c] = i;
c++;
if (c >= N) return;
}
for (int i = s-1; i >= -s; i--)
{
dx[c] = i;
dy[c] = -s;
c++;
if (c >= N) return;
}
}
}
signed main() {
cin.tie(0)->sync_with_stdio(0);
cin.exceptions(cin.failbit);
/*
5 1
..XX.
*/
fill();
// for (int i = 0; i < 20; i++)
// cout << i << " " << dx[i] << " " << dy[i] << "\n";
// return 0;
cin >> n >> m;
swap(n, m);
for (int i = 0; i < n; i++) {
string s;
cin >> s;
for (int j = 0; j < m; j++)
if (s[j] == 'X')
X[i][j] = 1;
}
vector<vector<pair<int, int> > > st(1);
for (int i=0; i<n; i++)
for (int j=0; j<m; j++)
st[0].pb({i, j});
int mx = 0;
for (int t = 0;; t++)
{
// cout<<"TTTTTTTTTT "<<t<<"\n";
// cout<<dx[t]<<" "<<dy[t]<<"\n";
// for (int i=0; i<sz(st); i++)
// {
// for (auto pa:st[i])
// cout<<pa.fi<<" "<<pa.se<<"\n";
// cout<<"\n";
// }
// cout<<endl;
vector<vector<pair<int, int> > > nt;
int id = 0;
for (const auto& v : st)
{
if (v.size() <= 1)
continue;
nt.pb({});
nt.pb({});
nt[id].reserve(v.size());
vector<pair<int, int> > a, b;
for (const auto& [x, y] : v)
if (get(x+dx[t], y+dy[t]))
nt[id].pb({x, y});
else
nt[id+1].pb({x, y});
id+=2;
}
st = nt;
if (st.size() == 0)
break;
for (const auto& v : st)
if (v.size() == 1)
T[v[0].fi][v[0].se] = t, mx = t;
}
int sum = 0;
for (int i=0; i<n; i++)
for (int j=0; j<m; j++)
sum += T[i][j];
// for (int i=0; i<n; i++, cout<<"\n")
// for (int j=0; j<m; j++)
// cout<<T[i][j]<<" ";
// for (int i=0; i<n; i++, cout<<"\n")
// for (int j=0; j<m; j++)
// cout<<X[i][j]<<" ";
cout<<fixed<<setprecision(10);
cout<<sum*1.0/n/m<<"\n";
cout<<mx<<"\n";
set<pair<int, int> > stx;
for (int i=0; i<n; i++)
for (int j=0; j<m; j++)
if (T[i][j] == mx)
stx.insert({j+1, n-i});
for (auto pa : stx)
cout<<"("<<pa.fi<<","<<pa.se<<") ";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 4684kb
input:
1 1 X
output:
0.0000000000 0 (1,1)
result:
ok correct!
Test #2:
score: 0
Accepted
time: 0ms
memory: 4824kb
input:
2 1 .X
output:
0.0000000000 0 (1,1) (2,1)
result:
ok correct!
Test #3:
score: 0
Accepted
time: 1ms
memory: 4704kb
input:
2 1 X.
output:
0.0000000000 0 (1,1) (2,1)
result:
ok correct!
Test #4:
score: 0
Accepted
time: 0ms
memory: 4932kb
input:
1 2 . X
output:
0.0000000000 0 (1,1) (1,2)
result:
ok correct!
Test #5:
score: 0
Accepted
time: 0ms
memory: 4824kb
input:
1 2 X .
output:
0.0000000000 0 (1,1) (1,2)
result:
ok correct!
Test #6:
score: 0
Accepted
time: 1ms
memory: 4916kb
input:
2 1 XX
output:
3.0000000000 3 (1,1) (2,1)
result:
ok correct!
Test #7:
score: 0
Accepted
time: 1ms
memory: 4684kb
input:
3 3 XXX X.X XXX
output:
3.1111111111 5 (3,1) (3,2)
result:
ok correct!
Test #8:
score: 0
Accepted
time: 808ms
memory: 5360kb
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: 668ms
memory: 5040kb
input:
100 100 X................................................................................................... .................................................................................................... .............................................................................................
output:
19735.3199000000 39599 (100,1) (100,2)
result:
ok correct!
Test #10:
score: 0
Accepted
time: 698ms
memory: 5112kb
input:
100 100 .................................................................................................... .................................................................................................... .............................................................................................
output:
19865.6699000000 39500 (100,1) (100,2)
result:
ok correct!
Test #11:
score: -100
Wrong Answer
time: 951ms
memory: 5560kb
input:
100 100 X................................................................................................... .X.................................................................................................. ..X..........................................................................................
output:
11855.6392000000 39302 (99,100) (100,99)
result:
wrong answer Read (99,100) but expected (100,99)