QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#613220 | #6124. King Of Zombies | qtoq | WA | 40ms | 4024kb | C++17 | 3.5kb | 2024-10-05 13:46:17 | 2024-10-05 13:47:07 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }
void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#ifdef ONPC
#define deb(...) cerr << '[' << __FILE__ << ':' << __LINE__ << "] (" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define deb(...)
#endif
// c++ short types
#define vt vector
//typedef long long ll;
typedef long double ld;
void whattime() { cout << "finished in " << clock() * 1.0 / CLOCKS_PER_SEC << " sec" << endl; }
// const int mod = 1e9 + 7;
const int mod = 998244353;
const int inf = 1e9;
const int64_t infll = 1e13;
bool debug = false;
const ld eps = 1e-9;
const ld pi = acos(-1);
mt19937_64 rng((int) chrono::steady_clock::now().time_since_epoch().count());
void solve() {
int n;
ld d;
cin >> n >> d;
vt<ld> x(n+1), y(n+1), vx(n+1), vy(n+1);
for(int i = 0; i <= n; ++i) {
cin >> x[i] >> y[i] >> vx[i] >> vy[i];
}
vt<int> used(n + 1, false);
vt<ld> dist(n + 1, 1e18);
set<pair<ld, int>> st;
auto Go = [&](int to, ld t) -> void {
deb(to, t);
if(used[to] == false || dist[to] > t) {
st.erase({dist[to], to});
st.insert({dist[to] = t, to});
}
};
auto Edge = [&](int from, int to, ld t) -> void {
ld vx1 = vx[from], vy1 = vy[from];
ld x1 = x[from] + t * vx1, y1 = y[from] + t * vy1;
ld vx2 = vx[to], vy2 = vy[to];
ld x2 = x[to] + t * vx2, y2 = y[to] + t * vy2;
if((x1-x2)*(x1-x2) + (y1-y1)*(y1-y2) <= d * d) {
deb("hi", from, to, t);
Go(to, t);
return ;
}
ld A = (vx1 - vx2)*(vx1 - vx2) + (vy1 - vy2)*(vy1 - vy2);
ld B = 2 * ((x1 - x2) * (vx1 - vx2) + (y1 - y2) * (vy1 - vy2));
ld C = (x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2) - d*d;
if (C <= 0) {
Go(to, t);
return ;
}
// Дискриминант
ld discriminant = B * B - 4 * A * C;
if (discriminant < 0) {
return ;
}
// Вычисляем два возможных момента времени касания
ld t1 = (-B + sqrtl(discriminant)) / (2 * A);
ld t2 = (-B - sqrtl(discriminant)) / (2 * A);
deb(from, to, t, t1, t2);
// Нам нужно положительное время
if (t1 >= 0 && t2 >= 0) {
Go(to, t + min(t1, t2));
} else if (t1 >= 0) {
Go(to, t + t1);
} else if (t2 >= 0) {
Go(to, t + t2);
}
};
Go(0, 0);
while(not st.empty()) {
auto [T, u] = *st.begin();
deb(T, u);
st.erase(st.begin());
if(used[u]) {
continue;
}
used[u] = 1;
for(int i = 0; i <= n; ++i) if(!used[i]) {
Edge(u, i, T);
}
}
cout << fixed << setprecision(12);
for(int i = 1; i <= n; ++i) {
if(!used[i]) {
cout << "-1\n";
} else {
cout << dist[i] << '\n';
}
}
}
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr);
int tt = 1;;
if(debug) {
tt = 1e3;
} else {
}
for(int t = 0; t < tt; ++t) {
solve();
}
#ifdef ONPC
whattime();
#endif
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 4024kb
input:
5 3 0 0 3 0 10 10 0 -3 1 1 -1 -1 16 1 -1 0 100 100 100 100 -100 -3 10 0
output:
2.626226552147 0.000000000000 3.000000000000 -1 14.285714285714
result:
ok 5 numbers
Test #2:
score: 0
Accepted
time: 0ms
memory: 3864kb
input:
4 10 0 0 0 0 10 0 0 0 20 0 0 0 30 0 0 0 41 0 0 0
output:
0.000000000000 0.000000000000 0.000000000000 -1
result:
ok 4 numbers
Test #3:
score: 0
Accepted
time: 40ms
memory: 4024kb
input:
814 5261 8674 -10000 83 9959 -3135 4963 -5450 -980 -6718 -5021 -5412 1206 8906 -9471 -4357 5471 -3795 2180 -4645 -2664 9110 -5528 9221 -3130 -3916 1465 -6825 5446 1767 -3479 -6871 -7960 -3523 5303 -1141 7806 3362 -3357 7529 -6106 -7323 -8776 3458 3288 -4825 -5940 -4857 95 -3169 6767 -3056 -2340 3228...
output:
0.000000000000 0.000000000000 0.000000000000 0.000000000000 0.000000000000 0.000000000000 0.000000000000 0.000000000000 0.000000000000 0.000000000000 0.000000000000 0.000000000000 0.000000000000 0.000000000000 0.000000000000 0.000000000000 0.000000000000 0.000000000000 0.000000000000 0.000000000000 ...
result:
ok 814 numbers
Test #4:
score: -100
Wrong Answer
time: 3ms
memory: 3912kb
input:
470 235 5883 -1751 1075 368 7790 2418 3758 -3846 -5164 -3433 -5837 -7492 -3987 -6763 6899 -9252 -7032 2446 -4829 6204 5952 -1391 -6466 -1366 1902 -976 -6563 3105 -726 2931 4726 5388 5891 -2901 -3071 906 1237 6576 -2018 1582 -4444 -974 -537 -7998 -5090 -3067 -6005 -6746 7139 -9713 -6108 5218 150 -569...
output:
0.000000000000 0.000000000000 0.000000000000 0.000000000000 0.000000000000 0.000000000000 0.000000000000 0.000000000000 0.000000000000 0.000000000000 0.000000000000 0.000000000000 0.000000000000 0.000000000000 0.000000000000 0.000000000000 0.000000000000 0.000000000000 0.000000000000 0.000000000000 ...
result:
wrong answer 1st numbers differ - expected: '-1.0000000', found: '0.0000000', error = '1.0000000'