QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#562345#8511. Greek Casinoucup-team3519#WA 36ms4572kbC++201.9kb2024-09-13 16:56:472024-09-13 16:56:51

Judging History

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

  • [2024-09-13 16:56:51]
  • 评测
  • 测评结果:WA
  • 用时:36ms
  • 内存:4572kb
  • [2024-09-13 16:56:47]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pi;
typedef double db;
#define V vector
#define pb push_back
#define fi first
#define se second
#define all1(x) (x).begin() + 1, (x).end()
const int INF = 2e9 + 10;

int main() {
    int n; cin >> n;
    V<int> w(n + 1);
    for(int i = 1; i <= n; i++) cin >> w[i];
    LL sum = accumulate(all1(w), 0);
    V<V<pi>> dis(n + 1);
    for(int i = 1; i <= n; i++) {
        int now = i;
        for(int j = 2; j * j <= now; j++) {
            int e = 1;
            if(now % j == 0) {
                e *= j;
                now /= j;
            }
            if(e != 1) dis[i].pb({j, e});
        }
        if(now != 1) dis[i].pb({now, now});
    }

    map<pi, int> mp;
    V<int> tmp(n + 1);
    for(int x = 1; x <= n; x++) {
        for(int y = x; y <= n; y += x) {
            tmp[y] = 0;
        }
        for(int y = x; y <= n; y += x) {
            for(int z = y; z <= n; z += y) tmp[z] += w[y];
        }
        for(int y = x; y <= n; y += x) {
            mp[{x, y}] = tmp[y];
        }
    }

    auto get_lb = [&](int i, int j) -> int {
        int l = 0, r = 0;
        int ans = 1;
        while(r != dis[j].size()) {
            if(l == dis[i].size() || dis[i][l] != dis[i][r]) {
                if(l != dis[i].size() && dis[i][l].fi == dis[i][r].fi) l++;
                ans *= dis[j][r].se;
                r++;
            } else {
                l++, r++;
            }
        }
        return ans;
    };

    V<db> dp(n + 1);
    for(int i = n; i >= 1; i--) {
        db pself = (db)mp[{get_lb(i, i), i}] / sum;
        db tmp = 1;
        for(int j = 2 * i; j <= n; j++) {
            tmp += (db)mp[{get_lb(i, j), j}] / sum * dp[j];
        }
        dp[i] = tmp * (1 / (1 - pself));
    }

    cout << fixed << setprecision(20) << dp[1] - 1 << endl;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3
1 1 1

output:

3.49999999999999911182

result:

ok found '3.500000000', expected '3.500000000', error '0.000000000'

Test #2:

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

input:

3
1 1 2

output:

3.66666666666666607455

result:

ok found '3.666666667', expected '3.666666667', error '0.000000000'

Test #3:

score: -100
Wrong Answer
time: 36ms
memory: 4572kb

input:

1337
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 1 1 1 1 1 1...

output:

2.64807707237969980341

result:

wrong answer 1st numbers differ - expected: '1.0183368', found: '2.6480771', error = '1.6003941'