QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#154733#5505. Great Chaseberarchegas#WA 814ms3804kbC++171.3kb2023-08-31 21:35:162023-08-31 21:35:17

Judging History

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

  • [2023-08-31 21:35:17]
  • 评测
  • 测评结果:WA
  • 用时:814ms
  • 内存:3804kb
  • [2023-08-31 21:35:16]
  • 提交

answer

#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using ld = long double;
using pld = pair<ld, ld>;

mt19937 rng((int) chrono::steady_clock::now().time_since_epoch().count());
    
const int MOD = 1e9 + 7;
const int MAXN = 4e5 + 5;
const ll INF = 2e12;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(15);
    int t;
    cin >> t;
    while(t--) {
        int n;
        ld vl;
        cin >> n >> vl;
        vector <pld> pos, neg;
        ld mx = 0;
        for(int i = 1; i <= n; i++) {
            ld p, v;
            cin >> p >> v;
            mx = max(mx, v);
            if(p < 0) neg.push_back({p, v});
            else pos.push_back({p, v});
        }
        ld ini = 0, fim = INF;
        for(int i = 0; i < 80; i++) {
            ld m = (ini + fim) / 2;
            ld mx = -INF, mn = INF;
            for(auto cur : neg) {
                mx = max(mx, cur.first + cur.second * m);
            }
            for(auto cur : pos) {
                mn = min(mn, cur.first - cur.second * m);
            }
            if(mx >= mn) fim = m;
            else ini = m;
        }
        cout << ini * vl << '\n';
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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.249999999998705
1.230769230762482
2999999999999.999999761581421

result:

ok 3 numbers

Test #2:

score: -100
Wrong Answer
time: 814ms
memory: 3804kb

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.349109321832657
16414958969.727279717102647
5202715639.835183573886752
321977234.156325340794865
45384199210.221683416515589
183885744.769230729769333
1708925225.230472021619789
89786664971.557941183447838
13924365606.287387385964394
412975327.555555497267051
965508404.512101212865673
4...

result:

wrong answer 4566th numbers differ - expected: '1.0000010', found: '1.0000001', error = '0.0000009'