QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#562374 | #8511. Greek Casino | ucup-team3519# | WA | 47ms | 4484kb | C++20 | 1.9kb | 2024-09-13 17:06:28 | 2024-09-13 17:06:29 |
Judging History
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];
int 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 pe = 1;
while(now % j == 0) {
pe *= j;
now /= j;
}
if(pe != 1) dis[i].pb({j, pe});
}
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[j][r]) {
if(l != dis[i].size() && dis[i][l].fi == dis[j][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: 3768kb
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: 3828kb
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: 47ms
memory: 4484kb
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:
1.34477024635345898673
result:
wrong answer 1st numbers differ - expected: '1.0183368', found: '1.3447702', error = '0.3205554'