QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#124902#5648. Crossing the RailwaysHongzy#WA 1ms3796kbC++174.3kb2023-07-15 18:12:582023-07-15 18:13:02

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-15 18:13:02]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3796kb
  • [2023-07-15 18:12:58]
  • 提交

answer

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT);
#define rep(i, j, k) for(int i = j; i <= k; ++ i)
#define per(i, j, k) for(int i = j; i >= k; -- i)
using namespace std;

#define fs first
#define sc second
#define pb push_back
#define mp make_pair

using db = double;
using ll = long long;
using uint = unsigned int;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

mt19937 mt(chrono::system_clock::now().time_since_epoch().count());
uniform_int_distribution<ll> ran(0, 1ll << 62);
void ucin() { ios::sync_with_stdio(0); cin.tie(0); }
// uniform_real_distribution<double> dbran;
template<class T> inline void chkmax(T &x, const T &y) { if(x < y) x = y; }
template<class T> inline void chkmin(T &x, const T &y) { if(x > y) x = y; }
inline ll sqr(ll x) { return x * x; }
inline ll cub(ll x) { return x * x * x; }

const int N = 510;
const int INF = 1e9;
const db eps = 1e-8;
#define lt(x, y) ((x) < (y) - eps)
#define leq(x, y) ((x) < (y) + eps)
struct seg {
  int r, a, b;
  bool operator < (const seg &rhs) const {
    if(r != rhs.r) return r < rhs.r;
    return a < rhs.a;
  }
} a[N];
int n, m, s;
db v;
int dp[N*2], X[N*2], Y[N*2];

bool inc(db l, db x, db r) {
  return lt(l, x) && lt(x, r);
}
bool inc(db x1, int y1, db x2, int y2) {
  assert(lt(x1, x2) && y1 < y2);
  rep(i, 1, n)
    if(inc(y1, a[i].r, y2)) {
      db k = (x2 - x1) / (y2 - y1);
      db b = x1 - k * y1;
      db x0 = k * a[i].r + b;
      if(inc(a[i].a, x0, a[i].b))
        return true;
    }

  return false;
}
int main() {
  scanf("%d%d%d%lf", &n, &m, &s, &v); v = 1/v;
  rep(i, 1, n) {
    int a, b, r;
    scanf("%d%d%d", &a, &b, &r);
    ::a[i] = {r, a, b};
  }
  sort(a + 1, a + n + 1);
  {
    db x0 = 0, x2 = (m + 1.0) / v;
    if(!inc(x0, 0, x2, m + 1) && leq(x2, s)) {
      puts("0");
      cerr << "**\n";
      return 0;
    }
  }

  dp[0] = 0;
  rep(i, 1, 2*n) {
    int y = a[(i + 1) / 2].r;
    int x = i & 1 ? a[(i + 1) / 2].a : a[(i + 1) / 2].b;
    X[i] = x, Y[i] = y;
    // printf("(%d, %d)\n", x, y);
  }
  //single point rush
  rep(i, 1, 2*n) {
    db x = X[i];
    int y = Y[i];
    db x2 = x + (m + 1.0 - y) / v;
    db x0 = x - y * 1.0 / v;
    if(leq(0, x0) && leq(x2, s) && !inc(x0, 0, x2, m + 1)) {
      puts("0");
      cerr << "()\n";
      return 0;
    }
  }
  rep(i, 1, 2*n)
    rep(j, i+1, 2*n)
      if(X[i] < X[j] && Y[i] < Y[j] && Y[j] - Y[i] <= v * (X[j] - X[i])) {
        // printf("(%d, %d)!\n", i, j);
        db k = (Y[j] - Y[i]) / db(X[j] - X[i]);
        db x0 = X[i] - k * Y[i], x2 = X[j] + k * (m + 1 - Y[j]);
        if(leq(0, x0) && leq(x2, s) && !inc(x0, 0, x2, m + 1)) {
          puts("0");
          cerr << "[]\n";
          return 0;
        }
      }

  int ans = INF;
  rep(i, 1, 2*n) {
    int x = X[i], y = Y[i];
    
    dp[i] = INF;
    db x0 = x - (db)y / v;
    if(leq(0, x0) && !inc(x0, 0, x, y)) {
      // printf("x0 = %.1f\n", x0);
      dp[i] = 0;
    } else {
      rep(j, 1, i-1) {
        if(x > X[j] && y > Y[j] && y - Y[j] <= 1LL * v * (x - X[j])) {
          db v0 = (y - Y[j]) / db(x - X[j]);
          db x0 = x - (db)y / v0;
          if(leq(0, x0) && !inc(x0, 0, x, y)) {
            dp[i] = 0;
            break;
          }
        }
      }
    }

    if(dp[i] == INF) {
      rep(j, 1, i-1)
        if(dp[j] + 1 < dp[i] && x > X[j] && y > Y[j] && y - Y[j] <= 1LL * v * (x - X[j])) {
          // printf("(%d -> %d\n", i, j);
          if(!inc(X[j], Y[j], x, y)) {
            // printf("%d -> %d\n", i, j);
            dp[i] = dp[j] + 1;
          }
        }
    }
    // printf("dp %d = %d\n", i, dp[i]);
    if(dp[i] < INF) {
      db x2 = x + (db)(m + 1 - y) / v;
      if(leq(x2, s) && !inc(x, y, x2, m + 1)) {
        // printf("%d -> end\n", i);
        ans = min(ans, dp[i] + 1);
      } else {
        rep(j, i+1, n) {
          if(x < X[j] && y < Y[j] && Y[j] - y <= 1LL * v * (X[j] - x)) {
            db v0 = (Y[j] - y) / db(X[j] - x);
            db x2 = x + (db)(m + 1 - y) / v0;
            if(leq(x2, s) && !inc(x, y, x2, m + 1)) {
              // printf("%d -> end\n", i);
              ans = min(ans, dp[i] + 1);
              break;
            }
          }
        }
      }
    }
  }
  if(ans == INF) ans = -1;
  printf("%d\n", ans);
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3640kb

input:

4 3 5 1
1 2 1
3 4 1
2 3 2
3 4 3

output:

0

result:

ok single line: '0'

Test #2:

score: 0
Accepted
time: 1ms
memory: 3668kb

input:

3 3 12 2
2 10 1
1 6 2
8 12 3

output:

2

result:

ok single line: '2'

Test #3:

score: 0
Accepted
time: 1ms
memory: 3676kb

input:

8 4 13 2
1 4 1
5 13 1
1 5 2
6 13 2
1 9 3
10 13 3
1 10 4
11 13 4

output:

2

result:

ok single line: '2'

Test #4:

score: 0
Accepted
time: 1ms
memory: 3556kb

input:

1 1 2 2
1 2 1

output:

-1

result:

ok single line: '-1'

Test #5:

score: 0
Accepted
time: 1ms
memory: 3716kb

input:

10 7 85 8
76 89 7
22 36 6
17 61 4
62 96 3
57 86 6
51 94 5
39 40 1
31 39 7
7 18 5
67 87 4

output:

-1

result:

ok single line: '-1'

Test #6:

score: 0
Accepted
time: 1ms
memory: 3672kb

input:

10 10 91 1
1 100 9
1 100 8
1 100 1
1 100 10
1 100 3
1 100 4
1 100 7
1 100 2
1 100 5
1 100 6

output:

-1

result:

ok single line: '-1'

Test #7:

score: 0
Accepted
time: 0ms
memory: 3796kb

input:

10 3 99994 12436
14053 20692 1
20693 72913 1
1 14052 1
36226 100000 3
1 5048 2
1 688 3
70945 100000 2
5049 70944 2
72914 100000 1
689 36225 3

output:

-1

result:

ok single line: '-1'

Test #8:

score: -100
Wrong Answer
time: 1ms
memory: 3708kb

input:

10 7 67853 3238
27043 44174 4
69150 89334 2
65082 73038 1
18887 34795 6
49387 76379 7
63582 76311 4
70393 78225 6
52699 81352 5
79076 90480 6
46727 51948 4

output:

1

result:

wrong answer 1st lines differ - expected: '0', found: '1'