QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#613237#6124. King Of ZombiesqtoqWA 25ms4060kbC++173.5kb2024-10-05 13:47:422024-10-05 13:48:59

Judging History

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

  • [2024-10-05 13:48:59]
  • 评测
  • 测评结果:WA
  • 用时:25ms
  • 内存:4060kb
  • [2024-10-05 13:47:42]
  • 提交

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(false && (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;
}


详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3848kb

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: 3732kb

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: -100
Wrong Answer
time: 25ms
memory: 4060kb

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:

wrong answer 768th numbers differ - expected: '0.0000000', found: '0.7216111', error = '0.7216111'