QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#96435#5153. Delft DistanceAhmed_Abdelmegeed#TL 4364ms71732kbC++204.9kb2023-04-13 21:28:262023-04-13 21:28:28

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 21:28:28]
  • 评测
  • 测评结果:TL
  • 用时:4364ms
  • 内存:71732kb
  • [2023-04-13 21:28:26]
  • 提交

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) {
            //cout << x << " " << y << " " << j << " " << cur + dis[x][y][i] << el;
            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) {
            //cout << x << " " << y << " " << j << " " << cur + dis[x][y][i] << el;
            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 - 1][2] = min(dis[x + 1][y - 1][2], dis[x][y][6]);
    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][6] = min(dis[x - 1][y + 1][6], dis[x][y][2]);
    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);
        zbtsquare(1, 1);
    }
    for (int i = 0; i < 8; i++) {
        pq.push({ -dis[1][1][i], {{1, 1}, i}});
        vis[1][1][i] = dis[1][1][i];
    }
    ld cost;
    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);
        for (int i = 0; i < 8; i++) {
            nx = x + dx[i], ny = y + dy[i];
            if (valid(nx, ny)) {
                zbtsquare(nx, ny);
                if (grid[nx][ny] == 'O') {
                    zbtcircle(nx, ny);
                    zbtsquare(nx, ny);
                }
            }
            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];
                    pq.push({ -dis[nx][ny][j], {{nx, ny}, j}});
                }
            }
        }
    }
}

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(10) << 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: 4ms
memory: 7648kb

input:

3 5
XOOXO
OXOXO
XXXXO

output:

71.4159265359

result:

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

Test #2:

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

input:

1 4
XOOX

output:

45.7079632679

result:

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

Test #3:

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

input:

1 1
X

output:

20.0000000000

result:

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

Test #4:

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

input:

1 1
O

output:

17.8539816340

result:

ok found '17.8539816', expected '17.8539816', error '0.0000000'

Test #5:

score: 0
Accepted
time: 3ms
memory: 7624kb

input:

1 3
XOO

output:

35.7079632679

result:

ok found '35.7079633', expected '35.7079633', error '0.0000000'

Test #6:

score: 0
Accepted
time: 3ms
memory: 5672kb

input:

1 5
OXOOO

output:

55.7079632679

result:

ok found '55.7079633', expected '55.7079633', error '0.0000000'

Test #7:

score: 0
Accepted
time: 5ms
memory: 7920kb

input:

6 10
XXXXXOOOOX
XXOOOOOOOO
XXXOXOOXOX
OXOXOXXOOX
OOXXOXXXXO
OXOXXOOXOO

output:

142.8318530718

result:

ok found '142.8318531', expected '142.8318531', error '0.0000000'

Test #8:

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

input:

1 2
XX

output:

30.0000000000

result:

ok found '30.0000000', expected '30.0000000', error '0.0000000'

Test #9:

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

input:

10 1
X
X
X
O
O
O
X
O
O
X

output:

105.7079632679

result:

ok found '105.7079633', expected '105.7079633', error '0.0000000'

Test #10:

score: 0
Accepted
time: 6ms
memory: 9808kb

input:

18 6
OOOOOO
OOOOOO
XOOOOO
OOOOXO
OOOXOO
OOOOOO
OOOOOO
OOOOOO
OOOOOX
OOOOOO
OOOXOO
OOOOOO
OOOOOO
OOOOOO
OOOOOO
OOOOOO
OOOOOO
OOOOOO

output:

214.2477796077

result:

ok found '214.2477796', expected '214.2477796', error '0.0000000'

Test #11:

score: 0
Accepted
time: 19ms
memory: 16080kb

input:

40 9
OOOOXOXXX
XOXXXOXXO
OXOXXXXXO
OXOXXXOXX
XXXXOXOXX
XXOOXOXXX
XOOXOXXXX
XOXXOOXOX
OXXOOOOXX
XXOOOXXOO
OXOOXOXXX
OOOOOXOOO
OXXXXXXXO
OOOOOOOXX
OOOXXXOOX
OXOXXOOOO
OOOOXOXOO
OXOXOOOXO
OXXOOXXXO
OXOOXOOXO
XXXOXOXOO
XXOOOXOOX
OOXXOOXOO
XOOXXXXOX
OXXXXOOOO
OXOOOOXOX
XXOXXXOOO
OOXOOOXXX
OXOOOOXOO
OXOOO...

output:

453.5176877776

result:

ok found '453.5176878', expected '453.5176878', error '0.0000000'

Test #12:

score: 0
Accepted
time: 58ms
memory: 16092kb

input:

41 50
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXO
XXXXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXOXXXXXXXXXXXXXXX
XXXXXXXXXXXXXOXXXXXXXXXXXXXXOXXXXXXXXXX...

output:

873.5176877776

result:

ok found '873.5176878', expected '873.5176878', error '0.0000000'

Test #13:

score: 0
Accepted
time: 4364ms
memory: 71732kb

input:

329 527
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

8560.0000000000

result:

ok found '8560.0000000', expected '8560.0000000', error '0.0000000'

Test #14:

score: 0
Accepted
time: 371ms
memory: 18656kb

input:

49 297
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

3451.4159265359

result:

ok found '3451.4159265', expected '3451.4159265', error '0.0000000'

Test #15:

score: 0
Accepted
time: 808ms
memory: 54640kb

input:

357 83
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

4342.0575041173

result:

ok found '4342.0575041', expected '4342.0575041', error '0.0000000'

Test #16:

score: -100
Time Limit Exceeded

input:

417 615
XXXXXXXXOXXXXXXXXXXXOXXXXXXXXXXXOXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXOXXXXXXXXXXXXXXOXXXXXOXXXOOXXXXXXXXXXXXXXXXXXXXXOXOXXOXXXXXXXXXXXXXOXXXXXXXXXXXXXXXXXXOXXXXXXOXXXXXXXXOXXXXXXXOXXXXXXXXXXXXXXXXOXXXXXXOXXXXXXXOXXXXXXXXXXOXXXXXXXXOXXXOXXXOXXXXXOXXXOXXXXXXXXXOXXXXXXXXXXXXXXXXXXXX...

output:


result: