QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#469071#5887. Safety in Numbershungt121 ✓386ms3748kbC++141.5kb2024-07-09 13:00:452024-07-09 13:00:45

Judging History

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

  • [2024-07-09 13:00:45]
  • 评测
  • 测评结果:21
  • 用时:386ms
  • 内存:3748kb
  • [2024-07-09 13:00:45]
  • 提交

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;
}

详细

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