QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#140747 | #5153. Delft Distance | Gamal74# | WA | 12ms | 76264kb | C++20 | 4.8kb | 2023-08-16 19:13:57 | 2023-08-16 19:13:58 |
Judging History
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'