QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#727352#5978. Runaway QuailSunsetGlow950 0ms0kbC++143.6kb2024-11-09 12:54:292024-11-09 12:54:29

Judging History

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

  • [2024-11-09 12:54:29]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:0kb
  • [2024-11-09 12:54:29]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

const int MXN = 505;
const double INF = 1e18;
int T, C, N, aid, bid;
int pos[MXN], spd[MXN], aps[MXN], bps[MXN];
double mnt[MXN][MXN][2], ans;

inline double gettime(double cur, double p, int tgt) {
//cout << "gettime " << cur << ' ' << p << ' ' << tgt << ' ';
  int v(pos[tgt] > 0 ? C : -C);
//cout << (pos[tgt] - p + cur * 1.0 * s) / (s - spd[tgt]) << endl;
  return (p - pos[tgt] - cur * v) / (spd[tgt] - v);
}
inline double getpos(int id, double t) {
  return pos[id] + t * spd[id];
}
inline pair<double, double> getlst(double cur, double p, int id) {
  int v(pos[id] < 0 ? C : -C);
  double tim = (p - pos[id] - cur * v) / (spd[id] - v);
  return make_pair(tim, getpos(id, tim));
}

int main() {
  freopen("tiii.in", "r", stdin);
  freopen("tiii.out", "w", stdout);
  scanf("%d", &T);
  while (T--) {
    scanf("%d%d", &C, &N), aid = bid = 0;
    for (int i(0); i != N; ++i) {
      scanf("%d", &pos[i]);
      if (pos[i] > 0) aps[aid++] = i;
      else bps[bid++] = i;
    }
    for (int i(0); i != N; ++i) {
      scanf("%d", &spd[i]);
      if (pos[i] < 0) spd[i] = -spd[i];
    }
    sort(aps, aps + aid, [](int x, int y) { return spd[x] > spd[y]; });
    sort(bps, bps + bid, [](int x, int y) { return spd[x] < spd[y]; });
    for (int i(0); i <= aid; ++i)
      for (int j(0); j <= bid; ++j) mnt[i][j][0] = mnt[i][j][1] = INF;
    ans = INF;
    mnt[0][0][0] = mnt[0][0][1] = 0;
    for (int i(0); i <= aid; ++i) {
      for (int j(0); j <= bid; ++j) {
//      cout << i << ' ' << j << " 0: " << mnt[i][j][0] << endl;
//      cout << i << ' ' << j << " 1: " << mnt[i][j][1] << endl;
        if (mnt[i][j][0] != INF) {
//        cout << i << ' ' << j << " 0:" << mnt[i][j][0] << endl;
          double curpos(i ? getpos(aps[i - 1], mnt[i][j][0]) : 0);
          bool lok(true), rok(true);
          for (int k(i); k != aid; ++k) {
            if (getpos(aps[k], mnt[i][j][0]) <= curpos) continue;
            mnt[k + 1][j][0] = min(mnt[k + 1][j][0],
                gettime(mnt[i][j][0], curpos, aps[k]));
            lok = false;
            break;
          }
          pair<double, double> lst(j ? getlst(mnt[i][j][0], curpos, bps[j - 1]) :
                                       make_pair(0.0, 0.0));
          for (int k(j); k != bid; ++k) {
            if (getpos(bps[k], lst.first) >= lst.second) continue;
            mnt[i][k + 1][1] = min(mnt[i][k + 1][1],
                gettime(mnt[i][j][0], curpos, bps[k]));
            rok = false;
            break;
          }
          if (lok && rok) ans = min(ans, mnt[i][j][0]);
        }

        if (mnt[i][j][1] != INF) {
//        cout << i << ' ' << j << " 1:" << mnt[i][j][1] << endl;
          double curpos = (j ? getpos(bps[j - 1], mnt[i][j][1]) : 0);
          bool lok = true, rok = true;
          for (int k(j); k != bid; ++k) {
            if (getpos(bps[k], mnt[i][j][1]) >= curpos) continue;
            mnt[i][k + 1][1] = min(mnt[i][k + 1][1],
                gettime(mnt[i][j][1], curpos, bps[k]));
            rok = false;
            break;
          }
          pair<double, double> lst(i ? getlst(mnt[i][j][1], curpos, aps[i - 1]) :
                                       make_pair(0.0, 0.0));
          for (int k(i); k != aid; ++k) {
            if (getpos(aps[k], lst.first) <= lst.second) continue;
            mnt[k + 1][j][0] = min(mnt[k + 1][j][0],
                gettime(mnt[i][j][1], curpos, aps[k]));
            lok = false;
            break;
          }
          if (lok && rok) ans = min(ans, mnt[i][j][1]);
        }
      }
    }
    printf("%.9lf\n", ans);
  }
  return 0;
}

详细

Subtask #1:

score: 0
Dangerous Syscalls

Test #1:

score: 0
Dangerous Syscalls

input:

50
4 3
-3 -6 -9
3 2 1
2 2
1 -1
1 1
1000 25
769234 -5735820 -524288 -5403090 -6429140 1574982 1 -9733628 -1407481 4093041 4117720 -3193501 -9765195 -3069520 1122216 -5799108 131072 -8482066 -256 -8021159 -8958386 -7027036 5370579 -3602534 -6834567
425 102 744 155 339 19 999 19 159 198 51 304 369 601 ...

output:


result:


Subtask #2:

score: 0
Dangerous Syscalls

Test #2:

score: 0
Dangerous Syscalls

input:

50
4 3
-3 -6 -9
3 2 1
2 2
1 -1
1 1
1000 500
-9650379 9806301 -6495789 -1283284 5022779 4725553 9364178 -8123302 -9609729 7847458 -142364 6983908 8147008 -3186924 7339254 -8737645 8757174 7887319 3609962 5780915 -1752801 -1657946 -9511339 5113995 -7887160 -6093170 260267 -3837106 -356098 6676924 6210...

output:


result: