QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#469071 | #5887. Safety in Numbers | hungt1 | 21 ✓ | 386ms | 3748kb | C++14 | 1.5kb | 2024-07-09 13:00:45 | 2024-07-09 13:00:45 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(false); cin.tie(0)
const double EPS = 1e-7;
void solve(int tc) {
cout << "Case #" << tc << ": ";
int n; cin >> n;
int sum = 0;
vector<int> s(n);
for (int &x : s) {
cin >> x;
sum += x;
}
auto check = [&](int idx, double p, double score) -> bool {
int cnt = 0;
int partial = 0;
for (int i = 0; i < n; i++) {
if (i == idx || s[i] > score)
continue;
cnt++;
partial += s[i];
}
double mean = (partial + sum * (1 - p)) / cnt;
return score >= mean;
};
vector<double> ans(n);
for (int i = 0; i < n; i++) {
double left = 0, right = 1;
double minVal = right;
for (int it = 0; it < 500; it++) {
double mid = (left + right) / 2;
double score = s[i] + sum * mid;
if (check(i, mid, score)) {
right = mid;
minVal = min(minVal, mid);
} else {
left = mid;
}
}
ans[i] = minVal;
}
cout << fixed << setprecision(6);
for (double x : ans) {
cout << x * 100 << " ";
}
cout << '\n';
}
int main()
{
fastio;
int T; cin >> T;
for (int tc = 0; tc < T; tc++){
solve(tc + 1);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 1ms
memory: 3720kb
input:
20 2 20 10 2 10 0 4 25 25 25 25 3 24 30 21 7 1 54 53 0 1 1 54 10 0 77 0 0 0 0 0 0 0 0 6 80 80 80 80 80 80 2 53 53 7 73 74 73 0 0 1 1 10 100 100 100 100 100 100 100 100 100 100 2 47 0 7 99 1 100 1 1 0 99 6 33 50 37 50 100 40 5 0 1 98 0 97 4 62 11 52 61 7 73 45 60 54 69 48 73 8 55 53 53 76 47 76 77 42...
output:
Case #1: 33.333333 66.666667 Case #2: 0.000000 100.000000 Case #3: 25.000000 25.000000 25.000000 25.000000 Case #4: 34.666667 26.666667 38.666667 Case #5: 24.847561 0.000000 0.000000 25.457317 24.847561 24.847561 0.000000 Case #6: 11.111111 0.000000 11.111111 11.111111 11.111111 11.111111 11.11...
result:
ok correct! (20 test cases)
Subtask #2:
score: 11
Accepted
Test #2:
score: 11
Accepted
time: 386ms
memory: 3748kb
input:
50 174 46 49 48 48 47 47 45 48 49 46 45 47 44 44 50 48 50 45 44 49 50 45 49 47 44 45 49 48 47 48 44 45 49 50 45 46 50 46 48 49 48 46 44 50 49 45 49 44 47 46 46 50 46 49 47 45 47 46 50 44 45 45 49 48 50 46 48 46 49 50 49 49 46 45 50 47 48 44 48 46 46 45 44 46 49 49 44 47 49 48 50 45 46 45 50 45 45 46...
output:
Case #1: 0.589633 0.553150 0.565311 0.565311 0.577472 0.577472 0.601794 0.565311 0.553150 0.589633 0.601794 0.577472 0.613955 0.613955 0.540989 0.565311 0.540989 0.601794 0.613955 0.553150 0.540989 0.601794 0.553150 0.577472 0.613955 0.601794 0.553150 0.565311 0.577472 0.565311 0.613955 0.601794 0.5...
result:
ok correct! (50 test cases)
Extra Test:
score: 0
Extra Test Passed