QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#95828#5593. Food ProcessorUsername#WA 38ms8768kbC++141.6kb2023-04-11 23:15:502023-04-11 23:15:53

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-11 23:15:53]
  • 评测
  • 测评结果:WA
  • 用时:38ms
  • 内存:8768kb
  • [2023-04-11 23:15:50]
  • 提交

answer

#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
using ld = long double;

struct stableSum {
    int cnt = 0;
    vector<ld> v, pref{0};
    void operator+=(ld a) {
        if (a < -1e-9) {
            cout << "-1\n"; exit(0);
        }
        int s = ++cnt;
        while (s % 2 == 0) {
            a += v.back();
            v.pop_back(), pref.pop_back();
            s /= 2;
        }
        v.push_back(a);
        pref.push_back(pref.back() + a);
    }
    ld val() { return pref.back(); }
};

void test_case() {
    cout << fixed << setprecision(12);
    int s, t, n;
    cin >> s >> t >> n;
    map<int, int, greater<int>> mp;
    for (int i = 0, m, h; i < n; ++i) {
        cin >> m >> h;
        int &x = mp[m];
        if (x == 0)
            x = h;
        else x = min(x, h);
    }
    vector<pair<int, int>> vp;
    for (auto p : mp)
        vp.push_back(p);
    if (s == t) {
        cout << "0\n"; return;
    }
    if (vp[0].F < s) {
        cout << "-1\n"; return;
    }
    stableSum ans;
    int mn = vp[0].S;
    for (int i = 1; i < vp.size(); ++i) {
        if (vp[i].F < t)
            break;
        if (vp[i].S >= mn)
            continue;
        ans += mn * log2(s * 1.0l / vp[i].F);
        mn = vp[i].S;
        s = vp[i].F;
    }
    ans += mn * log2(s * 1.0l / t);
    cout << ans.val() << '\n';
}

signed main() {
    ios::sync_with_stdio(false); cout.tie(nullptr); cin.tie(nullptr);
    test_case();
    // int tc; cin >> tc;
    // while (tc--) {
    //     test_case();
    // }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

10 1 2
10 10
4 5

output:

23.219280948874

result:

ok found '23.21928', expected '23.21928', error '0.00000'

Test #2:

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

input:

10000 9999 1
10000 1

output:

0.000144276718

result:

ok found '0.00014', expected '0.00014', error '0.00000'

Test #3:

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

input:

10 1 2
8 10
4 5

output:

-1

result:

ok found '-1.00000', expected '-1.00000', error '-0.00000'

Test #4:

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

input:

8 2 1
8 10

output:

20.000000000000

result:

ok found '20.00000', expected '20.00000', error '0.00000'

Test #5:

score: 0
Accepted
time: 38ms
memory: 8756kb

input:

1000000 1 100000
10 10
20 20
30 30
40 40
50 50
60 60
70 70
80 80
90 90
100 100
110 110
120 120
130 130
140 140
150 150
160 160
170 170
180 180
190 190
200 200
210 210
220 220
230 230
240 240
250 250
260 260
270 270
280 280
290 290
300 300
310 310
320 320
330 330
340 340
350 350
360 360
370 370
380 3...

output:

1442798.050879614644

result:

ok found '1442798.05088', expected '1442798.05088', error '0.00000'

Test #6:

score: 0
Accepted
time: 35ms
memory: 8756kb

input:

1000000 1 100000
1000000 10
999990 20
999980 30
999970 40
999960 50
999950 60
999940 70
999930 80
999920 90
999910 100
999900 110
999890 120
999880 130
999870 140
999860 150
999850 160
999840 170
999830 180
999820 190
999810 200
999800 210
999790 220
999780 230
999770 240
999760 250
999750 260
99974...

output:

199.315685693242

result:

ok found '199.31569', expected '199.31569', error '0.00000'

Test #7:

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

input:

1000000 999999 1
1000000 1

output:

0.000001442696

result:

ok found '0.00000', expected '0.00000', error '0.00000'

Test #8:

score: 0
Accepted
time: 2ms
memory: 3776kb

input:

1000000 1 1
1000000 999999

output:

19931548.637755604763

result:

ok found '19931548.63776', expected '19931548.63776', error '0.00000'

Test #9:

score: -100
Wrong Answer
time: 38ms
memory: 8768kb

input:

500000 12345 100000
4783 477451
939177 624790
942796 933658
388835 943838
591586 528454
934640 609727
702473 355566
440638 181750
957421 781586
785155 972417
184923 378838
791637 199851
268779 962854
866409 181893
288522 536245
889062 89973
535331 469534
740453 750376
26154 41835
470536 449187
72774...

output:

-1

result:

wrong answer 1st numbers differ - expected: '77.58570', found: '-1.00000', error = '1.01289'