QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#96315#5153. Delft DistanceAhmed_Abdelmegeed#WA 2ms7724kbC++205.0kb2023-04-13 19:23:112023-04-13 19:23:16

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-13 19:23:16]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:7724kb
  • [2023-04-13 19:23:11]
  • 提交

answer

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long
#define ld long double
#define el "\n"
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define ordered_multiset tree<ll, null_type,less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update>
using namespace __gnu_pbds;
using namespace std;
const ll N = 700 + 10, INF = 1e18;
const ld pi = acos(-1);
const int mod = 1e9 + 7, LOG = 20;
const ld eps = 1e-4;
int dx[] = {0, -1, 0, 1, -1, 1, -1, 1};
int dy[] = { -1, 0, 1, 0, 1, -1, -1, 1};
ll n, m, k, x, y;
ld sidecircle = 0.5 * pi * 5;
ld dis[N][N][10], vis[N][N][10];
char grid[N][N];

void zbtsquare(int x, int y) {
    ld cur;
    for (int i = 0; i < 8; i++) {
        cur = 0;
        for (int j = i; j < i + 8; j++) {
            dis[x][y][j % 8] = min(cur + dis[x][y][i], dis[x][y][j % 8]);
            cur += 5;
        }
        cur = 0;
        for (int j = i; j > i - 8; j--) {
            dis[x][y][(j + 8) % 8] = min(cur + dis[x][y][i], dis[x][y][(j + 8) % 8]);
            cur += 5;
        }
    }
}

void zbtcircle(int x, int y) {
    ld cur;
    for (int i = 1; i < 8; i += 2) {
        cur = 0;
        for (int j = i; j < i + 8; j += 2) {
            dis[x][y][j % 8] = min(cur + dis[x][y][i], dis[x][y][j % 8]);
            cur += sidecircle;
        }
        cur = 0;
        for (int j = i; j > i - 8; j -= 2) {
            dis[x][y][(j + 8) % 8] = min(cur + dis[x][y][i], dis[x][y][(j + 8) % 8]);
            cur += sidecircle;
        }
    }
}

bool valid(int x, int y) {
    return (x >= 1 && x <= n && y >= 1 && y <= m);
}

void trantition(int x, int y) {
    dis[x - 1][y][6] = min(dis[x - 1][y][6], dis[x][y][2]);
    dis[x][y + 1][0] = min(dis[x][y + 1][0], dis[x][y][2]);
    dis[x][y + 1][7] = min(dis[x][y + 1][7], dis[x][y][3]);
    dis[x][y + 1][6] = min(dis[x][y + 1][6], dis[x][y][4]);
    dis[x + 1][y + 1][0] = min(dis[x + 1][y + 1][0], dis[x][y][4]);
    dis[x + 1][y][2] = min(dis[x + 1][y][2], dis[x][y][4]);
    dis[x + 1][y][1] = min(dis[x + 1][y][1], dis[x][y][5]);
    dis[x + 1][y][0] = min(dis[x + 1][y][0], dis[x][y][6]);
    dis[x - 1][y + 1][2] = min(dis[x - 1][y + 1][2], dis[x][y][6]);
    dis[x][y - 1][2] = min(dis[x][y - 1][2], dis[x][y][0]);
    dis[x][y - 1][3] = min(dis[x][y - 1][3], dis[x][y][7]);
    dis[x][y - 1][4] = min(dis[x][y - 1][4], dis[x][y][6]);
    dis[x - 1][y - 1][4] = min(dis[x - 1][y - 1][4], dis[x][y][0]);
    dis[x - 1][y][6] = min(dis[x - 1][y][6], dis[x][y][0]);
    dis[x - 1][y][5] = min(dis[x - 1][y][5], dis[x][y][1]);
    dis[x - 1][y][4] = min(dis[x - 1][y][4], dis[x][y][2]);
}

void solve() {
    priority_queue<pair<ld, pair<pair<int, int>, int>>> pq;
    dis[1][1][0] = 0;
    zbtsquare(1, 1);
    if (grid[1][1] == 'O') {
        zbtcircle(1, 1);
    }
    for (int i = 0; i < 8; i++) {
        //cout << i << " " << dis[1][1][i] << el;
        pq.push({ -dis[1][1][i], {{1, 1}, i}});
        vis[1][1][i] = dis[1][1][i];
    }
    ld cost;
    //cout << "HERE" << el;
    int state, nx, ny;
    while (pq.size()) {
        x = pq.top().second.first.first;
        y = pq.top().second.first.second;
        cost = -pq.top().first;
        state = pq.top().second.second;
        pq.pop();
        if (dis[x][y][state] != cost) {
            continue;
        }
        trantition(x, y);
        //cout << x << " " << y << el;
        for (int i = 0; i < 8; i++) {
            nx = x + dx[i], ny = y + dy[i];
            for (int j = 0; j < 8; j++) {
                if (vis[nx][ny][j] > dis[nx][ny][j] && valid(nx, ny)) {
                    vis[nx][ny][j] = dis[nx][ny][j];
                    //cout << x << " " << y << " " << nx << " " << ny << el;
                    //cout << vis[nx][ny][j] << " " << dis[nx][ny][j] << el;
                    zbtsquare(nx, ny);
                    //cout << nx << " " << ny << el;
                    if (grid[nx][ny] == 'O') {
                        zbtcircle(nx, ny);
                    }
                    pq.push({ -dis[nx][ny][j], {{nx, ny}, j}});
                }
            }
        }
        //return;
    }
}

void dowork() {
    cin >> n >> m;
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            for (int k = 0; k <= 8; k++) {
                dis[i][j][k] = vis[i][j][k] = 2e18;
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> grid[i][j];
        }
    }
    solve();
    cout << fixed << setprecision(8) << dis[n][m][4] << el;
}

signed main() {
    fast
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    int t = 1;
    //cin >> t;
    for (int i = 1; i <= t; i++) {
        dowork();
    }
    return 0;
}

詳細信息

Test #1:

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

input:

3 5
XOOXO
OXOXO
XXXXO

output:

71.41592654

result:

ok found '71.4159265', expected '71.4159265', error '0.0000000'

Test #2:

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

input:

1 4
XOOX

output:

45.70796327

result:

ok found '45.7079633', expected '45.7079633', error '0.0000000'

Test #3:

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

input:

1 1
X

output:

20.00000000

result:

ok found '20.0000000', expected '20.0000000', error '0.0000000'

Test #4:

score: -100
Wrong Answer
time: 0ms
memory: 5784kb

input:

1 1
O

output:

20.00000000

result:

wrong answer 1st numbers differ - expected: '17.8539816', found: '20.0000000', error = '0.1201983'