QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#390077#5112. Where Am I?0_GB_RAM#WA 951ms5560kbC++233.5kb2024-04-15 02:41:092024-04-15 02:41:10

Judging History

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

  • [2024-04-15 02:41:10]
  • 评测
  • 测评结果:WA
  • 用时:951ms
  • 内存:5560kb
  • [2024-04-15 02:41:09]
  • 提交

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<<") ";

}

詳細信息

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)