QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#373107#5112. Where Am I?RobeZH#WA 14ms9680kbC++233.2kb2024-04-01 02:35:032024-04-01 02:35:05

Judging History

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

  • [2024-04-01 02:35:05]
  • 评测
  • 测评结果:WA
  • 用时:14ms
  • 内存:9680kb
  • [2024-04-01 02:35:03]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define subnb true
#define Lnb true
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;

struct P {
    vi vs;
    int x, y;
};

const int INF = (int)1e9;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;
    swap(n, m);
    vector<string> str(n);
    vector<pii> mks;
    rep(i, 0, n) {
        cin >> str[i];
        rep(j, 0, m) {
            if(str[i][j] == 'X') {
                mks.push_back({i, j});
            }
        }
    }
    int C = 200;
    vector<pii> ps;
    vector<vi> seq(2 * C, vi(2 * C, 0));
    int x = C, y = C;
    auto in_bound = [&](int x, int y) {
        return 0 <= x && x < 2 * C && 0 <= y && y < 2 * C;
    };
    auto mv_d = [&](int dx, int dy, int step) {
        while(step--) {
            seq[x][y] = sz(ps);
            ps.push_back({x - C, y - C});
            x += dx;
            y += dy;
            if(!in_bound(x, y)) return false;
        }
        return true;
    };
    for(int s = 1; ; s++) {
        if(s % 2 == 1) {
            if(!mv_d(-1, 0, s)) break;
            if(!mv_d(0, 1, s)) break;
        } else {
            if(!mv_d(1, 0, s)) break;
            if(!mv_d(0, -1, s)) break;
        }
    }

    vector<P> xs;
    rep(i, 0, n) {
        rep(j, 0, m) {
            vi vs;
            for (auto p : mks) {
                vs.push_back(seq[p.first - i + C][p.second - j + C]);
            }
            sort(all(vs));
            xs.push_back({vs, i, j});
//            cout << i << ", " << j << ": ";
//            for (int y : vs) cout << y << " ";
//            cout << endl;
        }
    }
    sort(all(xs), [](const P &p1, const P &p2) {
        return p1.vs < p2.vs;
    });
    vector<vi> res(n, vi(m));
    vi lcp(sz(xs));
    rep(i, 1, sz(xs)) {
        int cur = 0;
        while(xs[i].vs[cur] == xs[i - 1].vs[cur]) cur++;
        lcp[i] = min(xs[i].vs[cur], xs[i - 1].vs[cur]);
//        cout << i << ": " << lcp[i] << endl;
    }
    ll sum = 0;
    int mx = 0;
    vector<pii> mxs;
    rep(i, 0, sz(xs)) {
        int ans = max((i > 0 ? lcp[i] : 0), (i + 1 < sz(xs) ? lcp[i + 1] : 0));
//        cout << lcp[i] << " " << lcp[i + 1] << ", " << ans << endl;
        res[xs[i].x][xs[i].y] = ans;
//        cout << xs[i].x << " " << xs[i].y << ": ";
//        for (int x : xs[i].vs) cout << x << " ";
//        cout << ", ans: " << ans << endl;
//        cout << endl;
        sum += ans;
        if(ans > mx) {
            mx = ans;
            mxs = {{xs[i].y, xs[i].x }};
        } else if(ans == mx) {
            mxs.push_back({xs[i].y, xs[i].x});
        }
    }
    ld ev = (ld)sum / n / m;
    cout << fixed << setprecision(10) << ev << '\n';
    cout << mx << '\n';
    for (auto &p : mxs) {
        p.second = n - 1 - p.second;
    }
    sort(all(mxs));
    for (auto p : mxs) cout << "(" << p.first + 1 << "," << (p.second) + 1 << ") ";
    cout << '\n';


}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 5888kb

input:

1 1
X

output:

0.0000000000
0
(1,1) 

result:

ok correct!

Test #2:

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

input:

2 1
.X

output:

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

result:

ok correct!

Test #3:

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

input:

2 1
X.

output:

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

result:

ok correct!

Test #4:

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

input:

1 2
.
X

output:

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

result:

ok correct!

Test #5:

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

input:

1 2
X
.

output:

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

result:

ok correct!

Test #6:

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

input:

2 1
XX

output:

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

result:

ok correct!

Test #7:

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

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: 8728kb

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: 4ms
memory: 5956kb

input:

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

output:

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

result:

ok correct!

Test #10:

score: 0
Accepted
time: 1ms
memory: 5996kb

input:

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

output:

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

result:

ok correct!

Test #11:

score: -100
Wrong Answer
time: 14ms
memory: 9680kb

input:

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

output:

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

result:

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