QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#140747#5153. Delft DistanceGamal74#WA 12ms76264kbC++204.8kb2023-08-16 19:13:572023-08-16 19:13:58

Judging History

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

  • [2023-08-16 19:13:58]
  • 评测
  • 测评结果:WA
  • 用时:12ms
  • 内存:76264kb
  • [2023-08-16 19:13:57]
  • 提交

answer

#include<bits/stdc++.h>

#define ll long long
#define pp push_back
#define endl '\n'
#define all(x) x.begin(),x.end()
#define ld long double
#define PI acos(-1)
#define sin(a) sin((a)*PI/180)
#define cos(a) cos((a)*PI/180)
#define ones(x) __builtin_popcountll(x)
//#define int ll

using namespace std;

void Drakon() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef Clion
    freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
#endif
}

unsigned long long inf = 1e10;
const double EPS = 1e-6;
const int MOD = 1000000007, N = 1505, LOG = 25;

ll gcd(ll x, ll y) {
    return y ? gcd(y, x % y) : x;
}

ll lcm(ll a, ll b) {
    return (a * b) / __gcd(a, b);
}

ll mul(const ll &a, const ll &b) {
    return (a % MOD + MOD) * (b % MOD + MOD) % MOD;
}

ll add(const ll &a, const ll &b) {
    return (a + b + 2 * MOD) % MOD;
}

ll pw(ll x, ll y) {
    ll ret = 1;
    while (y > 0) {
        if (y % 2 == 0) {
            x = mul(x, x);
            y = y / 2;
        } else {
            ret = mul(ret, x);
            y = y - 1;
        }
    }
    return ret;
}

vector<pair<pair<int, int>, double>>adj[N][N];
double dist[N][N];
bool vis[N][N];

void dijkstra(){
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            dist[i][j] = 1e18;
        }
    }
    dist[0][0] = 0;
    priority_queue<pair<double, pair<int, int>>, vector<pair<double, pair<int, int>>>, greater<>>q;
    q.push({0, {0, 0}});

    while (!q.empty()){
        auto p = q.top();
        q.pop();
        int x = p.second.first, y = p.second.second;
        double d = p.first;
        if(vis[x][y])continue;
        vis[x][y] = true;

        for(auto v : adj[x][y]){
            if(dist[v.first.first][v.first.second] > d + v.second){
                dist[v.first.first][v.first.second] = d + v.second;
                q.push({dist[v.first.first][v.first.second], v.first});
            }
        }
    }
}

void solve() {
    int n, m;
    cin >> n >> m;
    char arr[n][m];
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> arr[i][j];
        }
    }

    double a = 5.0 / 2 * PI, b = 5 * PI;

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            int top = i * 10, bot = top + 10;
            int left = j * 10, right = left + 10;
            vector<pair<int, int>> corners = {{top, left},
                                              {top, right},
                                              {bot, right},
                                              {bot, left}};
            vector<pair<int, int>> circle = {{top, left + 5},
                                             {top + 5, right},
                                             {bot, left + 5},
                                             {top + 5, left}};

            for (int k = 0; k < 4; ++k) {
                corners[k].first /= 5;corners[k].second /= 5;
                circle[k].first /= 5; circle[k].second /= 5;
            }

            vector<int>dist1 = {10, 20, 10};
            for (int k = 0; k < 4; ++k) {
                int cur = 0;
                for (int l = (k + 1) % 4; cur < 3; l = (l + 1) % 4) {
                    if(k == l)continue;
                    adj[corners[k].first][corners[k].second].pp({corners[l], dist1[cur]});
                    adj[corners[l].first][corners[l].second].pp({corners[k], dist1[cur]});
                    cur ++;
                }
            }

            if(arr[i][j] == 'O'){
                vector<double>dist2 = {5 + a, 5 + a};
                for (int k = 0; k < 4; ++k) {
                    int cur = 0;
                    for (int l = (k + 1) % 4; cur < 2; l = (l + 1) % 4) {
                        adj[corners[k].first][corners[k].second].pp({circle[l], dist2[cur]});
                        adj[circle[l].first][circle[l].second].pp({corners[k], dist2[cur]});
                        cur ++;
                    }
                }

                dist2 = {a, b, a};
                for (int k = 0; k < 4; ++k) {
                    int cur = 0;
                    for (int l = (k + 1) % 4; cur < 3; l = (l + 1) % 4) {
                        if(k == l)continue;
                        adj[circle[k].first][circle[k].second].pp({circle[l], dist2[cur]});
                        adj[circle[l].first][circle[l].second].pp({circle[k], dist2[cur]});
                        cur ++;
                    }
                }
            }
        }
    }

    dijkstra();

    cout << fixed << setprecision(10) << dist[((n - 1) * 10 + 10) / 5][((m - 1) * 10 + 10) / 5];
}

signed main() {
    Drakon();
    int t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 12ms
memory: 75212kb

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: 12ms
memory: 76264kb

input:

1 4
XOOX

output:

45.7079632679

result:

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

Test #3:

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

input:

1 1
X

output:

20.0000000000

result:

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

Test #4:

score: -100
Wrong Answer
time: 8ms
memory: 75000kb

input:

1 1
O

output:

20.0000000000

result:

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