QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#615670 | #6124. King Of Zombies | qtoq | Compile Error | / | / | C++17 | 5.2kb | 2024-10-05 19:44:52 | 2024-10-05 19:44:53 |
Judging History
answer
//thatsramen
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define eb emplace_back
#define pb push_back
#define ft first
#define sd second
#define pi pair<int, int>
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define dbg(...) dbg_out(__VA_ARGS__)
using ll = long long;
using ld = long double;
using namespace std;
using namespace __gnu_pbds;
//Constants
const ll INF = 5 * 1e18;
const int IINF = 2 * 1e9;
const ll MOD = 1e9 + 7;
// const ll MOD = 998244353;
const ll dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const ld PI = 3.14159265359;
//Templates
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) {return os << '(' << p.first << ", " << p.second << ')';}
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...); }
template<typename T> bool mins(T& x, T y) { if (x > y) { x = y; return true; } return false; }
template<typename T> bool maxs(T& x, T y) { if (x < y) { x = y; return true; } return false; }
template<typename T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T> using omset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
//order_of_key(k): number of elements strictly less than k
//find_by_order(k): k-th element in the set
void setPrec() {cout << fixed << setprecision(15);}
void unsyncIO() {cin.tie(0)->sync_with_stdio(0);}
void setIn(string s) {freopen(s.c_str(), "r", stdin);}
void setOut(string s) {freopen(s.c_str(), "w", stdout);}
void setIO(string s = "") {
unsyncIO(); setPrec();
if(s.size()) setIn(s + ".in"), setOut(s + ".out");
}
// #define TEST_CASES
struct human {
pair<ld, ld> cord;
pi vel;
};
const ld eps = 1e-8;
void solve() {
int n, d;
cin >> n >> d;
vector<human> al(n+1);
for (int i = 0; i <= n; i++) {
cin >> al[i].cord.ft >> al[i].cord.sd;
cin >> al[i].vel.ft >> al[i].vel.sd;
}
auto get = [&](int i, int j, ld t) -> ld {
auto [x1, y1] = al[i].cord;
auto [vx1, vy1] = al[i].vel;
x1 += t * vx1;
y1 += t * vy1;
auto [x2, y2] = al[j].cord;
auto [vx2, vy2] = al[j].vel;
x2 += t * vx2;
y2 += t * vy2;
// if (1ll * (x2-x1) * (vy1-vy2) == 1ll * (y2-y1)*(vx1-vx2)) {
// if ((x2-x1 >= 0 && vx1-vx2 >= 0) || (x2-x1 >= 0 && vx1-vx2 >= 0)) {
// }
// }
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) {
return 0;
}
// Дискриминант
ld discriminant = B * B - 4 * A * C;
if (discriminant < 0) {
// Нет реального решения, нет касания
return INF; // Возвращаем отрицательное значение как индикатор отсутствия касания
}
// Вычисляем два возможных момента времени касания
ld t1 = (-B + sqrtl(discriminant)) / (2 * A);
ld t2 = (-B - sqrtl(discriminant)) / (2 * A);
// Нам нужно положительное время
if(t1 > -eps && t2 > - eps) {
return max(0., min(t1, t2));
} else if (t1 > -eps) {
return max(0., t1);
} else if (t2 > -eps) {
return max(0., t2);
} else {
return INF; // Касания не произойдет
}
return INF;
};
// for (int i = 0; i <= n; i++) {
// auto [tx, ty] = al[i].cord;
// auto [vx, vy] = al[i].vel;
// // dbg(i, tx +3 * vx, ty + 3 * vy);
// }
vector<ld> dist(n+1, INF);
dist[0] = 0;
priority_queue<pair<ld, int>> que;
vector<bool> vis(n + 1, false);
que.push({0, 0});
while (!que.empty()) {
auto [_, v] = que.top();
que.pop();
if (vis[v]) {
continue;
}
vis[v] = true;
for (int i = 1; i <= n; i++) {
// dbg(v, i, get(v, i), dist);
ld val = get(v, i, dist[v]);
if (dist[i] > dist[v] + val) {
dist[i] = dist[v] + val;
que.push({-dist[i], i});
}
}
}
// dbg(dist);
for (int i = 1; i <= n; i++) {
if (dist[i] > INF / 1000) {
cout << -1 << '\n';
continue;
}
cout << dist[i] << '\n';
}
}
int main() {
setIO();
int tt = 1;
#ifdef TEST_CASES
cin >> tt;
#endif
while (tt--)
solve();
return 0;
}
Details
answer.code: In lambda function: answer.code:103:23: error: no matching function for call to ‘max(double, const long double&)’ 103 | return max(0., min(t1, t2)); | ~~~^~~~~~~~~~~~~~~~~ In file included from /usr/include/c++/13/algorithm:60, from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51, from answer.code:3: /usr/include/c++/13/bits/stl_algobase.h:257:5: note: candidate: ‘template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)’ 257 | max(const _Tp& __a, const _Tp& __b) | ^~~ /usr/include/c++/13/bits/stl_algobase.h:257:5: note: template argument deduction/substitution failed: answer.code:103:23: note: deduced conflicting types for parameter ‘const _Tp’ (‘double’ and ‘long double’) 103 | return max(0., min(t1, t2)); | ~~~^~~~~~~~~~~~~~~~~ /usr/include/c++/13/bits/stl_algobase.h:303:5: note: candidate: ‘template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)’ 303 | max(const _Tp& __a, const _Tp& __b, _Compare __comp) | ^~~ /usr/include/c++/13/bits/stl_algobase.h:303:5: note: template argument deduction/substitution failed: answer.code:103:23: note: deduced conflicting types for parameter ‘const _Tp’ (‘double’ and ‘long double’) 103 | return max(0., min(t1, t2)); | ~~~^~~~~~~~~~~~~~~~~ In file included from /usr/include/c++/13/algorithm:61: /usr/include/c++/13/bits/stl_algo.h:5795:5: note: candidate: ‘template<class _Tp> constexpr _Tp std::max(initializer_list<_Tp>)’ 5795 | max(initializer_list<_Tp> __l) | ^~~ /usr/include/c++/13/bits/stl_algo.h:5795:5: note: template argument deduction/substitution failed: answer.code:103:23: note: mismatched types ‘std::initializer_list<_Tp>’ and ‘double’ 103 | return max(0., min(t1, t2)); | ~~~^~~~~~~~~~~~~~~~~ /usr/include/c++/13/bits/stl_algo.h:5805:5: note: candidate: ‘template<class _Tp, class _Compare> constexpr _Tp std::max(initializer_list<_Tp>, _Compare)’ 5805 | max(initializer_list<_Tp> __l, _Compare __comp) | ^~~ /usr/include/c++/13/bits/stl_algo.h:5805:5: note: template argument deduction/substitution failed: answer.code:103:23: note: mismatched types ‘std::initializer_list<_Tp>’ and ‘double’ 103 | return max(0., min(t1, t2)); | ~~~^~~~~~~~~~~~~~~~~ answer.code:105:23: error: no matching function for call to ‘max(double, ld&)’ 105 | return max(0., t1); | ~~~^~~~~~~~ /usr/include/c++/13/bits/stl_algobase.h:257:5: note: candidate: ‘template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)’ 257 | max(const _Tp& __a, const _Tp& __b) | ^~~ /usr/include/c++/13/bits/stl_algobase.h:257:5: note: template argument deduction/substitution failed: answer.code:105:23: note: deduced conflicting types for parameter ‘const _Tp’ (‘double’ and ‘ld’ {aka ‘long double’}) 105 | return max(0., t1); | ~~~^~~~~~~~ /usr/include/c++/13/bits/stl_algobase.h:303:5: note: candidate: ‘template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)’ 303 | max(const _Tp& __a, const _Tp& __b, _Compare __comp) | ^~~ /usr/include/c++/13/bits/stl_algobase.h:303:5: note: template argument deduction/substitution failed: answer.code:105:23: note: deduced conflicting types for parameter ‘const _Tp’ (‘double’ and ‘ld’ {aka ‘long double’}) 105 | return max(0., t1); | ~~~^~~~~~~~ /usr/include/c++/13/bits/stl_algo.h:5795:5: note: candidate: ‘template<class _Tp> constexpr _Tp std::max(initializer_list<_Tp>)’ 5795 | max(initializer_list<_Tp> __l) | ^~~ /usr/include/c++/13/bits/stl_algo.h:5795:5: note: template argument deduction/substitution failed: answer.code:105:23: note: mismatched types ‘std::initializer_list<_Tp>’ and ‘double’ 105 | return max(0., t1); | ~~~^~~~~~~~ /usr/include/c++/13/bits/stl_algo.h:5805:5: note: candidate: ‘template<class _Tp, class _Compare> constexpr _Tp std::max(initializer_list<_Tp>, _Compare)’ 5805 | max(initializer_list<_Tp> __l, _Compare __comp) | ^~~ /usr/include/c++/13/bits/stl_algo.h:5805:5: note: template argument deduction/substitution failed: answer.code:105:23: note: mismatched types ‘std::initializer_list<_Tp>’ and ‘double’ 105 | return max(0., t1); | ~~~^~~~~~~~ answer.code:107:23: error: no matching function for call to ‘max(double, ld&)’ 107 | return max(0., t2); | ~~~^~~~~~~~ /usr/include/c++/13/bits/stl_algobase.h:257:5: note: candidate: ‘template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)’ 257 | max(const _T...