QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#580563 | #8958. Neutral Spectator | fractal# | WA | 130ms | 9416kb | C++17 | 2.0kb | 2024-09-21 22:27:48 | 2024-09-21 22:27:49 |
Judging History
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'