QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#734253 | #5205. Game of Questions | cyj888 | AC ✓ | 821ms | 1023852kb | C++14 | 1.6kb | 2024-11-11 08:05:00 | 2024-11-11 08:05:01 |
Judging History
answer
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define ott(i,l,r) for (register int i = l; i <= r; i ++)
#define tto(i,l,r) for (register int i = r; i >= l; i --)
using namespace std;
int read () {
int x = 0; bool f = false; char c = getchar ();
while (!isdigit (c)) f |= (c == '-'), c = getchar ();
while (isdigit (c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar ();
return f ? -x : x;
}
typedef long long ll;
typedef long double ld;
const int N = 2e5 + 110, M = 1 << 17;
int n, m, siz;
vector <pair <int, int> > g[M];
ld f[N]; char ch[17];
int cnt[N];
int main () {
n = read (), m = read (), siz = 1 << m;
ott (s, 0, siz - 1) {
int len = 1 << __builtin_popcount (s);
g[s].resize (len);
for (int t = s; t; t = (t - 1) & s) g[s][-- len].fi = t;
g[s][-- len].fi = 0; assert (!len);
}
ott (i, 1, n) {
int s = 0; scanf ("%s", ch);
ott (j, 0, m - 1) if (ch[j] ^ '0') s |= 1 << j;
++ g[siz - 1][s].se;
}
tto (s, 0, siz - 2) {
int k; ott (j, 0, m - 1) if (!(s >> j & 1)) {
k = j; break;
}
int t = s | (1 << k);
for (auto x : g[s]) cnt[x.fi] = 0;
for (auto x : g[t]) cnt[s & x.fi] += x.se;
for (auto &x : g[s]) x.se = cnt[x.fi];
}
ott (s, 0, siz - 1) {
if ((s + 1) & 1) continue;
int c = n - g[s][0].se - g[s][(int)g[s].size () - 1].se;
if (!c) f[s] = 1.0;
else {
for (auto x : g[s]) {
int t = x.fi;
if (t && t ^ s)
f[s] += f[t] * x.se;
}
f[s] /= c;
}
}
printf ("%.12Lf\n", f[siz - 1]);
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 7076kb
input:
1 5 11010
output:
1.000000000000
result:
ok found '1.000000000', expected '1.000000000', error '0.000000000'
Test #2:
score: 0
Accepted
time: 1ms
memory: 7960kb
input:
3 3 011 101 110
output:
0.333333333333
result:
ok found '0.333333333', expected '0.333333333', error '0.000000000'
Test #3:
score: 0
Accepted
time: 1ms
memory: 7548kb
input:
6 4 1011 0110 1111 0110 0000 1101
output:
0.166666666667
result:
ok found '0.166666667', expected '0.166666667', error '0.000000000'
Test #4:
score: 0
Accepted
time: 0ms
memory: 6912kb
input:
1 2 00
output:
1.000000000000
result:
ok found '1.000000000', expected '1.000000000', error '0.000000000'
Test #5:
score: 0
Accepted
time: 0ms
memory: 10660kb
input:
1 2 11
output:
1.000000000000
result:
ok found '1.000000000', expected '1.000000000', error '0.000000000'
Test #6:
score: 0
Accepted
time: 1ms
memory: 7568kb
input:
2 5 10011 01111
output:
0.000000000000
result:
ok found '0.000000000', expected '0.000000000', error '-0.000000000'
Test #7:
score: 0
Accepted
time: 1ms
memory: 8876kb
input:
5 2 11 11 11 01 10
output:
0.500000000000
result:
ok found '0.500000000', expected '0.500000000', error '0.000000000'
Test #8:
score: 0
Accepted
time: 2ms
memory: 8100kb
input:
10 10 0110100110 1100101110 1011100110 0011001011 1100101000 0010001001 1101100111 0000001101 1100000011 1100111100
output:
0.103009259259
result:
ok found '0.103009259', expected '0.103009259', error '0.000000000'
Test #9:
score: 0
Accepted
time: 0ms
memory: 8292kb
input:
100 10 1000101100 0011110101 1101010000 1011101011 0001000111 1110111101 1010001110 0000110111 1101110001 0000110010 1001111111 1010100001 1110000111 1111000111 1110101010 1101000101 1000010110 0110110100 0100001000 1000001001 0111100010 0100011110 0100111111 1000110000 0111010011 0110000100 1001101...
output:
0.118796767214
result:
ok found '0.118796767', expected '0.118796767', error '0.000000000'
Test #10:
score: 0
Accepted
time: 12ms
memory: 23012kb
input:
10000 13 0101111101110 1010110100101 1000011001110 0110001100100 1011011000111 0111111101111 0100111101111 1110001011100 0100011000110 0000110010101 0101100000111 0010010101001 1010001001100 0010101001100 1001011000010 0001101100001 0100111000011 1001100110111 0001001001111 1000000010101 00111000111...
output:
0.074748534063
result:
ok found '0.074748534', expected '0.074748534', error '0.000000000'
Test #11:
score: 0
Accepted
time: 101ms
memory: 119884kb
input:
100000 15 010101111010100 111100100000101 110010011010010 111000011011011 010101001100001 110111000011110 000011010000101 100100001001111 000101111001000 011101001000110 100011011110001 000111101100110 101110100000111 001000011011100 010011110010110 101111111100011 100110100000110 011101110100110 11...
output:
0.065734766331
result:
ok found '0.065734766', expected '0.065734766', error '0.000000000'
Test #12:
score: 0
Accepted
time: 298ms
memory: 345556kb
input:
200000 16 0001110111010101 1001011100001110 0001110100100111 0101000101000001 0010010011001011 0101111000000011 1011010000110001 1100111100101000 1110110100000100 0000010010110100 0101101101111100 0111001111001100 1000101011101010 0110100011001000 1010100111011100 0000101101010001 0010001011000000 0...
output:
0.062727405372
result:
ok found '0.062727405', expected '0.062727405', error '0.000000000'
Test #13:
score: 0
Accepted
time: 821ms
memory: 1023028kb
input:
200000 17 11000001110100100 10101000100010101 00011000101010000 01111000011000100 11000111100001101 10101011010111000 00011011011001011 10110100010000110 11001111101010001 01010000110011100 01001011100111000 00011100110100010 11000100001100011 10011001100001111 11110110001001110 10001100000100110 11...
output:
0.058572616424
result:
ok found '0.058572616', expected '0.058572616', error '0.000000000'
Test #14:
score: 0
Accepted
time: 6ms
memory: 9108kb
input:
200000 2 10 11 11 01 01 11 00 01 10 00 10 00 11 00 00 11 00 01 01 10 11 01 11 10 11 11 01 01 10 10 00 00 01 11 10 01 10 10 10 10 11 00 00 10 11 01 10 11 10 10 00 10 01 11 00 11 01 01 10 11 01 01 01 00 11 10 10 10 11 11 10 01 10 00 00 01 00 00 10 01 01 01 01 00 00 11 11 00 10 10 11 11 00 00 01 10 00 ...
output:
0.500941261290
result:
ok found '0.500941261', expected '0.500941261', error '0.000000000'
Test #15:
score: 0
Accepted
time: 779ms
memory: 1023564kb
input:
1 17 01011010000010110
output:
0.000000000000
result:
ok found '0.000000000', expected '0.000000000', error '-0.000000000'
Test #16:
score: 0
Accepted
time: 8ms
memory: 7492kb
input:
200000 2 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ...
output:
1.000000000000
result:
ok found '1.000000000', expected '1.000000000', error '0.000000000'
Test #17:
score: 0
Accepted
time: 544ms
memory: 1023284kb
input:
1 17 00000000000000000
output:
1.000000000000
result:
ok found '1.000000000', expected '1.000000000', error '0.000000000'
Test #18:
score: 0
Accepted
time: 4ms
memory: 10332kb
input:
200000 2 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 ...
output:
1.000000000000
result:
ok found '1.000000000', expected '1.000000000', error '0.000000000'
Test #19:
score: 0
Accepted
time: 495ms
memory: 1023852kb
input:
1 17 11111111111111111
output:
1.000000000000
result:
ok found '1.000000000', expected '1.000000000', error '0.000000000'
Test #20:
score: 0
Accepted
time: 559ms
memory: 1023736kb
input:
200000 17 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00...
output:
1.000000000000
result:
ok found '1.000000000', expected '1.000000000', error '0.000000000'
Test #21:
score: 0
Accepted
time: 795ms
memory: 1022772kb
input:
200000 17 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00100000000000000 00010000000000000 00000000000000000 00000000000010000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000001100000 00000000000000000 00...
output:
0.059148256607
result:
ok found '0.059148257', expected '0.059148257', error '0.000000000'
Test #22:
score: 0
Accepted
time: 821ms
memory: 1023724kb
input:
200000 17 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000010000000 00000000000100000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00010000000000000 10000000000000000 00000000000000000 00000000000000000 00000000010000000 00000001000100000 00...
output:
0.057211446454
result:
ok found '0.057211446', expected '0.057211446', error '0.000000000'
Test #23:
score: 0
Accepted
time: 781ms
memory: 1023612kb
input:
200000 17 00100000010001001 00000000000000000 00000000000000000 00100100001000000 01010000000000001 00010000000000000 00000000000000000 00010000000000000 00000000000000000 00000000000000000 10000100000000000 00001000000000000 00000000000100000 00000000000000000 00000000000000000 00000000000010010 00...
output:
0.059417783155
result:
ok found '0.059417783', expected '0.059417783', error '0.000000000'
Test #24:
score: 0
Accepted
time: 783ms
memory: 1022640kb
input:
200000 17 00100000100000000 00000100001000000 00100001000000010 01010000010001011 00000000000000000 00000011010010011 10011000000000000 00000000101001000 00000000101000000 00000000010100001 00000000000000000 00000000001000100 00000000111000010 00001000000000110 01001010000000000 00000001000000000 10...
output:
0.059216849922
result:
ok found '0.059216850', expected '0.059216850', error '0.000000000'
Test #25:
score: 0
Accepted
time: 815ms
memory: 1022800kb
input:
200000 17 00000101010001001 00110001000001100 00001000000010001 10000100010000001 10000101000100000 10110000100100010 10010000111000000 00001000000000011 11100000000111100 10001000000010000 00101111000011010 10101000000000000 11001111000001000 00001000000010000 01000001100000111 10000001000111000 00...
output:
0.058793189979
result:
ok found '0.058793190', expected '0.058793190', error '0.000000000'
Test #26:
score: 0
Accepted
time: 811ms
memory: 1022848kb
input:
200000 17 00000101000101000 01010001000101001 11110110110101110 11000011010010011 11000000100101000 10100000111101001 00001110101001100 00011010110001000 01101100011000010 10000110001101011 10000001000010000 11100000100100001 01011101001000001 00001001100000111 00010001111011100 11000110000111100 00...
output:
0.058908055488
result:
ok found '0.058908055', expected '0.058908055', error '0.000000000'
Test #27:
score: 0
Accepted
time: 812ms
memory: 1022484kb
input:
200000 17 11011011001011010 11111101011101011 11010110101110011 00110101110010111 01011011010111010 01100011000000001 10101100111100011 01111110110100011 00110000011001111 01101010011010111 11010111110101011 01111110001110110 01110100100101111 10111000101110101 11111100111001101 00111111110101011 11...
output:
0.058816145260
result:
ok found '0.058816145', expected '0.058816145', error '0.000000000'
Test #28:
score: 0
Accepted
time: 805ms
memory: 1023736kb
input:
200000 17 10011011100011010 01111101101011110 11101101111111101 01111111100101101 01010101110011111 00111111111111001 01111101111110011 11111110110111010 11111010111111111 11111111111111111 11011111011101111 10111011111101011 01110001101110110 11110101110111111 11111111010111100 11011001001110111 11...
output:
0.058630576020
result:
ok found '0.058630576', expected '0.058630576', error '0.000000000'
Test #29:
score: 0
Accepted
time: 797ms
memory: 1023144kb
input:
200000 17 11111101111101111 11110111101111101 01111111011111111 10111111111101111 11110111111111111 11110110111010111 01110011111111111 11110110011110001 11111111001111111 01111111111111111 01111111110111111 11111111111101111 11011111111101111 01111111110110111 11111111101110101 11111111011101111 11...
output:
0.060236344825
result:
ok found '0.060236345', expected '0.060236345', error '0.000000000'
Test #30:
score: 0
Accepted
time: 795ms
memory: 1023568kb
input:
200000 17 11111111011111111 01111111111111111 11111111111111111 11111111111111111 11111111111111111 11111111111111111 01011111110111111 10111111111111011 11111111111111111 11111111111111101 11111111101111111 11111111111001101 11111011111111111 11111111111111110 11011111111111111 11111111111111011 11...
output:
0.057955394337
result:
ok found '0.057955394', expected '0.057955394', error '0.000000000'
Test #31:
score: 0
Accepted
time: 800ms
memory: 1023740kb
input:
200000 17 11111111111111111 11111111111111111 11111111111111111 11111111111111111 11111101111111111 11111111111111111 11111111111111111 11111111111111111 11111111111111111 11111111111111111 11011111111111111 11111111111111111 11111110111111111 11111111111111111 11111111111111111 11111111111111111 11...
output:
0.056681540367
result:
ok found '0.056681540', expected '0.056681540', error '0.000000000'
Test #32:
score: 0
Accepted
time: 788ms
memory: 1022584kb
input:
200000 17 11111111111111111 11111111111111111 11110111111111111 11111111111111111 11111111111111111 11111111111111111 11111111111111111 11111111111111111 11111111111111111 11011111111111111 11111111111111111 11111111111111111 11111111111111111 11111111110111111 11111111111111111 11111111111111111 11...
output:
0.059233909027
result:
ok found '0.059233909', expected '0.059233909', error '0.000000000'
Test #33:
score: 0
Accepted
time: 507ms
memory: 1023308kb
input:
200000 17 11111111111111111 11111111111111111 11111111111111111 11111111111111111 11111111111111111 11111111111111111 11111111111111111 11111111111111111 11111111111111111 11111111111111111 11111111111111111 11111111111111111 11111111111111111 11111111111111111 11111111111111111 11111111111111111 11...
output:
1.000000000000
result:
ok found '1.000000000', expected '1.000000000', error '0.000000000'