QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#108044 | #4228. Double Sort | zaxwellmen | WA | 701ms | 124772kb | C++20 | 1.2kb | 2023-05-23 15:05:30 | 2023-05-23 15:05:31 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef double db;
typedef pair<int, int> pi;
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) FOR(i, 0, a)
#define rsz resize
#define mp make_pair
int n, m;
vector<db> dp[51][10001];
db fact[10001], ch[10001][51];
// db choose(int n, int k) {
// if (pre.find(mp(n,k)) != pre.end()) return pre[mp(n,k)];
// if (k > n) return 0;
// db ans = 1;
// F0R(i, k) ans *= db(n-i) / db(i+1);
// pre[mp(n,k)] = ans;
// return ans;
// }
int main() {
cin.tie(0) -> sync_with_stdio(0);
fact[0] = 1;
FOR(i, 1, 10001) fact[i] = fact[i-1]*i;
F0R(k, 51) FOR(n, k, 10001) ch[n][k] = fact[n] / (fact[k] * fact[n-k]);
cin >> n >> m;
FOR(i, 1, n+1) {
FOR(j, i, m+1) {
dp[i][j].assign(i,1);
FOR(k, max(0, 2*i-j), i+1) {
db prob = ch[i][k] * ch[j-i][i-k] / ch[j][i];
FOR(a, k, i) dp[i][j][a] += dp[i-k][j-i][a-k] * prob;
}
}
}
cout << fixed << setprecision(8);
FOR(i, 1, n) dp[n][m][i] += dp[n][m][i-1];
// cout << "done" << endl;
F0R(i, n) cout << dp[n][m][i] << '\n';
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 19556kb
input:
3 5
output:
1.00000000 2.30000000 4.50000000
result:
ok 3 numbers
Test #2:
score: 0
Accepted
time: 4ms
memory: 19656kb
input:
5 17
output:
1.13138332 2.74838397 5.18309632 8.85568843 15.00000000
result:
ok 5 numbers
Test #3:
score: -100
Wrong Answer
time: 701ms
memory: 124772kb
input:
50 10000
output:
-nan -nan -nan -nan -nan -nan -nan -nan -nan -nan -nan -nan -nan -nan -nan -nan -nan -nan -nan -nan -nan -nan -nan -nan -nan -nan -nan -nan -nan -nan -nan -nan -nan -nan -nan -nan -nan -nan -nan -nan -nan -nan -nan -nan -nan -nan -nan -nan -nan -nan
result:
wrong output format Expected double, but "-nan" found