QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#580563#8958. Neutral Spectatorfractal#WA 130ms9416kbC++172.0kb2024-09-21 22:27:482024-09-21 22:27:49

Judging History

This is the latest submission verdict.

  • [2024-09-21 22:27:49]
  • Judged
  • Verdict: WA
  • Time: 130ms
  • Memory: 9416kb
  • [2024-09-21 22:27:48]
  • Submitted

answer

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

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()


void solve() {
    int n, m, Q;
    cin >> n >> m >> Q;
    vector<int> a(n), b(n), c(m), d(m);
    for (int &i : a) cin >> i;
    for (int &i : b) cin >> i;
    for (int &i : c) cin >> i;
    for (int &i : d) cin >> i;
    vector<double> p(n), q(m), prp(n), prq(m), sfp(n), sfq(m);
    while (Q--) {
        int x, y;
        cin >> x >> y;
        double l = 0, r = 2000;
        for (int it = 0; it < 80; it++) {
            double md = (l + r) / 2.0;
            for (int i = 0; i < n; ++i) 
                p[i] = a[i] - b[i] * md;
            for (int i = 0; i < m; ++i) 
                q[i] = d[i] * md - c[i];
            for (int i = 0; i < n; ++i) {
                if (i % x == 0) prp[i] = p[i];
                else prp[i] = min(prp[i - 1], p[i]);
            }
            reverse(all(p));
            for (int i = 0; i < n; ++i) {
                if (i % x == 0) sfp[i] = p[i];
                else sfp[i] = min(sfp[i - 1], p[i]);
            }
            reverse(all(p)), reverse(all(sfp));
            for (int i = 0; i < m; ++i) {
                if (i % y == 0) prq[i] = q[i];
                else prq[i] = max(prq[i - 1], q[i]);
            }
            reverse(all(q));
            for (int i = 0; i < m; ++i) {
                if (i % y == 0) sfq[i] = q[i];
                else sfq[i] = max(sfq[i - 1], q[i]);
            }
            reverse(all(q)), reverse(all(sfq));
            double mn = -1e9, mx = 1e9;
            for (int i = 0; i + x - 1 < n; ++i)
                mn = max(mn, min(sfp[i], prp[i + x - 1]));
            for (int i = 0; i + y - 1 < m; ++i)
                mx = min(mx, max(sfq[i], prq[i + y - 1]));
            if (mn >= mx) l = md;
            else r = md;
        }
        cout << setprecision(9) << fixed << l << '\n';
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int T;
    cin >> T;
    while (T--) solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2
3 4 5
1 1 1
2 3 4
6 7 8 9
5 6 7 8
1 1
1 2
2 1
3 3
3 4
1 1 1
1000
1
1
1000
1 1

output:

1.000000000
1.000000000
0.909090909
0.800000000
0.777777778
1.000000000

result:

ok 6 numbers

Test #2:

score: 0
Accepted
time: 125ms
memory: 9348kb

input:

1
100000 100000 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

1.000000000

result:

ok found '1.0000000', expected '1.0000000', error '0.0000000'

Test #3:

score: -100
Wrong Answer
time: 130ms
memory: 9416kb

input:

1
100000 100000 1
15 22 3 21 5 7 31 2 13 15 17 9 34 13 15 4 26 5 18 19 51 37 27 36 51 6 49 4 41 54 54 30 64 13 57 22 14 12 79 24 10 25 49 58 11 17 5 10 15 78 93 42 83 27 17 17 4 34 56 2 5 92 95 49 72 13 69 48 35 105 67 55 38 24 26 15 4 36 81 13 64 86 24 28 26 74 51 77 87 44 136 61 20 5 7 98 31 6 24 ...

output:

0.008484848

result:

wrong answer 1st numbers differ - expected: '0.0070707', found: '0.0084848', error = '0.0014141'