QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#373699 | #5205. Game of Questions | InfinityNS# | AC ✓ | 1133ms | 15576kb | C++14 | 1.4kb | 2024-04-01 23:53:39 | 2024-04-01 23:53:40 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ldb double
const int N=200050;
const int M=17;
char s[N];
int cnt[1<<M][M+1];
int q[N],m;
ldb ans=0;
ldb dp[1<<M];
bool was[1<<M];
int in[1<<M];
void Solve(int mask,int lvl){
if(was[mask])return;
was[mask]=true;
cnt[0][lvl]=0;
cnt[mask][lvl]=0;
int tot=0;
for(int i=mask;i;i=(i-1)&mask){
tot+=cnt[i][lvl];
}
if(tot==0){
if(mask&1){
ans+=dp[mask];
}
}else{
for(int i=(mask-1)&mask;i;i=(i-1)&mask){
dp[i]+=dp[mask]*(ldb)cnt[i][lvl]/tot;
}
for(int i=0;i<m;i++){
if(mask>>i&1){
int nxt=mask^(1<<i);
in[nxt]--;
if(in[nxt]==0){
for(int j=mask;j;j=(j-1)&mask){
cnt[j][lvl+1]=0;
}
for(int j=mask;j;j=(j-1)&mask){
int tmp=j;
if(j>>i&1)tmp-=1<<i;
cnt[tmp][lvl+1]+=cnt[j][lvl];
}
Solve(nxt,lvl+1);
}
}
}
}
}
int main(){
int n;
scanf("%i %i",&n,&m);
for(int i=1;i<=n;i++){
scanf("%s",s);
for(int j=0;j<m;j++){
if(s[j]=='1'){
q[i]+=1<<j;
}
}
}
for(int i=1;i<=n;i++){
cnt[q[i]][0]++;
}
for(int mask=0;mask<(1<<m);mask++){
for(int i=0;i<m;i++){
if(mask>>i&1){
in[mask^(1<<i)]++;
}
}
/*for(int sub=(mask-1)&mask;sub;sub=(sub-1)&mask){
in[sub]++;
}*/
}
dp[(1<<m)-1]=1;
Solve((1<<m)-1,0);
printf("%.12lf\n",ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 5928kb
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: 5904kb
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: 5912kb
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: 1ms
memory: 5948kb
input:
1 2 00
output:
1.000000000000
result:
ok found '1.000000000', expected '1.000000000', error '0.000000000'
Test #5:
score: 0
Accepted
time: 1ms
memory: 5936kb
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: 7952kb
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: 5868kb
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: 1ms
memory: 5976kb
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: 7920kb
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: 8128kb
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: 102ms
memory: 10132kb
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: 340ms
memory: 11004kb
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: 1132ms
memory: 15548kb
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: 5976kb
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: 1038ms
memory: 15564kb
input:
1 17 01011010000010110
output:
0.000000000000
result:
ok found '0.000000000', expected '0.000000000', error '-0.000000000'
Test #16:
score: 0
Accepted
time: 7ms
memory: 5956kb
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: 8ms
memory: 8340kb
input:
1 17 00000000000000000
output:
1.000000000000
result:
ok found '1.000000000', expected '1.000000000', error '0.000000000'
Test #18:
score: 0
Accepted
time: 7ms
memory: 5976kb
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: 5ms
memory: 6428kb
input:
1 17 11111111111111111
output:
1.000000000000
result:
ok found '1.000000000', expected '1.000000000', error '0.000000000'
Test #20:
score: 0
Accepted
time: 18ms
memory: 6480kb
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: 1126ms
memory: 15544kb
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: 1125ms
memory: 15528kb
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: 1120ms
memory: 15528kb
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: 1116ms
memory: 15524kb
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: 1122ms
memory: 15524kb
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: 1117ms
memory: 15464kb
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: 1133ms
memory: 15504kb
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: 1119ms
memory: 15572kb
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: 1115ms
memory: 15576kb
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: 1104ms
memory: 15524kb
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: 1115ms
memory: 15508kb
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: 1106ms
memory: 15556kb
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: 23ms
memory: 6776kb
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'