QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#507206#5505. Great ChaseNYCU_MyGO#AC ✓493ms19476kbC++205.8kb2024-08-06 13:39:042024-08-06 13:39:04

Judging History

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

  • [2024-08-06 13:39:04]
  • 评测
  • 测评结果:AC
  • 用时:493ms
  • 内存:19476kb
  • [2024-08-06 13:39:04]
  • 提交

answer

#ifndef NYCU_MyGO
#define NYCU_MyGO
#include NYCU_MyGO __FILE__ NYCU_MyGO

const double INF = 1e13;

void solve() {
    int N; cin >> N;
    double V; cin >> V;
    
    vector<pii> cops_l, cops_r;
    for (int i = 0; i < N; ++i) {
        int p, v; cin >> p >> v;
        if (p < 0) cops_l.eb(-p, v);
        if (p > 0) cops_r.eb( p, v);
    }
    sort(ALL(cops_l)), sort(ALL(cops_r));
    
    double ans = 0.0;
    double lo = -cops_l[0].first, hi = cops_r[0].first, mi;
    for (int _round = 1; _round <= 50; ++_round) {
        mi = (lo + hi) / 2.0;
        
        double min_time_l = INF, min_time_r = INF;
        for (auto [p, v] : cops_l) chmin(min_time_l, (p + mi) / v);
        for (auto [p, v] : cops_r) chmin(min_time_r, (p - mi) / v);
        ans = V * min_time_l;
        
        if (min_time_l > min_time_r) hi = mi;
        else                         lo = mi;
    }
    cout << fixed << setprecision(15) << ans << "\n";
}

int32_t main() {
    fastIO();
    
    int t = 1; cin >> t;
    for (int _ = 1; _ <= t; ++_) {
        solve();
    }
    
    return 0;
}

#else

#ifdef local
#define _GLIBCXX_DEBUG 1
#endif
#pragma GCC optimize("Ofast", "unroll-loops")
#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
#define int i64
using f80 = long double;
#define dobule f80
using pii = pair<int, int>;
template <typename T> using Prior = std::priority_queue<T>;
template <typename T> using prior = std::priority_queue<T, vector<T>, greater<T>>;

#define eb emplace_back
#define ef emplace_front
#define ee emplace
#define pb pop_back
#define pf pop_front
#define ALL(x) begin(x), end(x)
#define RALL(x) rbegin(x), rend(x)
#define SZ(x) ((int)(x).size())

#ifdef local
#define fastIO() void()
#define debug(...) \
    fprintf(stderr, "\u001b[33m"), \
    fprintf(stderr, "At [%s], line %d: (%s) = ", __FUNCTION__, __LINE__, #__VA_ARGS__), \
    _do(__VA_ARGS__), \
    fprintf(stderr, "\u001b[0m")
template <typename T> void _do(T &&_t) { cerr << _t << "\n"; }
template <typename T, typename ...U> void _do(T &&_t, U &&..._u) { cerr << _t << ", ", _do(_u...); }
#else
#define fastIO() ios_base::sync_with_stdio(0), cin.tie(0)
#define debug(...) void()
#endif

template <typename T, typename U> bool chmin(T &lhs, U rhs) { return lhs > rhs ? lhs = rhs, 1 : 0; }
template <typename T, typename U> bool chmax(T &lhs, U rhs) { return lhs < rhs ? lhs = rhs, 1 : 0; }

#endif

/*
                                                                                                                
                                                                                                                
                                                                                                                
                           iiiiii         iiiiiiiiii       iiiiiiiiiiiiii                                       
                      iiiiiiiiiiiii   iiiiiii    iiii    iiiiiiiiiiiiiii                          ii   iiii     
                   iiiiiiii     iiiiiiiii         iiii       iiii iii              iii          iiiiiiiiii      
                iiiiiii          iiiiii           iiii    iiii   ii           iiiiiiiiii      iiii iiii         
              iiiiii            iiiii             iiii iiii        iii      iiii    iiiiiiiiiiiiiiiii  ii       
            iiiiii            iiiiiii            iiiiiii       iiiiiiii   iii    iiiiiiiiiiiiii iii  iiii       
          iiiiii             iiiiiii            iiiii   ii   iiii       iiiiiiiiiii iiii  iii iiii iiii      iii
         iiiii              iiiiiiii       ii        iiiii iiii    iiiiiiiii        iii iii  iii  iii  ii  iiii 
       iiiiii              iiiiiiii      iiiii     iiiii iiiiiiiiiiiiiiii         iii  iii  ii  iii  iii iiii   
      iiiii                 iiiiii     iiii     iiiiii iiiiiii    iii iii       iiii  ii   i   ii  iii  iii     
    iiiiii                            iiii  iiiiiiiiiiiiiii       iii iiii   iiiii  iii  ii  iii  iii  ii       
   iiiii                              iiiiiiii iiiiiiiiii       iiii   iiiiiiiii            ii  iii  ii         
  iiiii                                     iiiiii  iiii      iiiii              iii      ii   ii  i            
iiiiii                                  iiiiiiii   iiiii    iiiii                        ii  ii   ii            
iiiii                                iiii  iiii    iiiiiiiiiiii                             ii                  
 iii                              iiii   iiii       iiiiiiii                                                    
                               iiiii   iiii                                                                     
                             iiii     iiii                                                                      
                           iiii    iiiii                                                                        
                         iii     iiiii                                                                          
                       iii     iiiii                                                                            
                      iii   iiiiii                                                                              
                      iiiiiiiii                                                                                 
                      iiiiii                                                                                    
                                                                                                                
                                                                                                                
                                                                                                                
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3
4 9
10 2
-7 2
-6 1
7 1
2 8
-1 7
1 6
2 3
-1000000000000 1
1000000000000 1

output:

38.250000000000028
1.230769230769232
3000000000000.005371093750000

result:

ok 3 numbers

Test #2:

score: 0
Accepted
time: 367ms
memory: 3940kb

input:

10000
200 997007
405524182320 754760
686939601648 419804
687047488212 715566
1446157132 4594
-670522037 4673
763634629282 253755
424307411732 275041
1582708381 8473
-667425982 4622
-522841486 1427
702430907988 460271
1405423646 1060
1497754648 6227
883363410675 723547
56899800372 46435
-810216390 64...

output:

145405766328.349060058593750
16414958969.727273941040039
5202715639.835216522216797
321977234.156325340270996
45384199210.221733093261719
183885744.769230872392654
1708925225.230470418930054
89786664971.557937622070312
13924365606.287395477294922
412975327.555555462837219
965508404.512101411819458
4...

result:

ok 10000 numbers

Test #3:

score: 0
Accepted
time: 455ms
memory: 4312kb

input:

93
15435 968117
4196666 184
-5069875 255
-9782648 980
-1978138 176
9333323 764
-4323540 12
-8442049 319
-5371878 137
2881306 10
-4050629 133
-4659099 59
-5189169 320
-2256647 99
-3686648 37
1059255 33
-223142 20
8040933 408
8407764 705
694547 38
-7913614 746
-3573355 132
5919585 189
-3756662 94
-795...

output:

189662921.363637089729309
197971181.333333522081375
997533531.737629532814026
6439673170.665739059448242
993821598110.661132812500000
22727977326.402664184570312
34702455207.518470764160156
677770533.929817557334900
46631726883.969131469726562
5446481867.129054069519043
11336247450.272098541259766
4...

result:

ok 93 numbers

Test #4:

score: 0
Accepted
time: 493ms
memory: 19476kb

input:

5
400000 999972
172811492468 106699
171900177092 102097
194121748377 184014
190302947556 172722
183121572232 149212
196566712700 190884
171376795991 99358
522927044000 159597
-129031052077 34395
189422320931 170012
-275879974024 638546
408864707565 98475
-106703244806 368801
192128798630 178213
2915...

output:

519985220219.812072753906250
511413015796.766235351562500
424240880533.634277343750000
518849481155.503601074218750
1882496988186.444091796875000

result:

ok 5 numbers

Test #5:

score: 0
Accepted
time: 469ms
memory: 8788kb

input:

38
16668 999947
-3844782803 511
-210897941456 464872
618726004990 714384
-954596898686 225256
96675744 1148
-1515974078 11375
-206213840984 706184
306078847 3947
-474818331950 391451
-616022698917 561244
123378707 1540
-640636592655 406006
459201391325 908506
-733249583 5719
496163273 6238
619876911...

output:

89670748252.978500366210938
98630840901.507675170898438
29393530999.894336700439453
50801000770.955986022949219
39668001027.269332885742188
467846478226.411437988281250
30789914370.571952819824219
23151476830.905101776123047
51606123416.625823974609375
151713060001.662597656250000
100944679009.60929...

result:

ok 38 numbers