QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#329969 | #6611. United in Stormwind | Ogiso_Setsuna | WA | 1ms | 3616kb | C++14 | 1.2kb | 2024-02-17 10:05:32 | 2024-02-17 10:05:34 |
Judging History
answer
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
typedef long long ll;
const int N=(1<<20)+5;
double Cor[2][2]={{1,0},{1,1}},Cand[2][2]={{1,1},{0,1}},Cxor[2][2]={{1,1},{1,-1}},
ICor[2][2]={{1,0},{-1,1}},ICand[2][2]={{1,-1},{0,1}},ICxor[2][2]={{0.5,0.5},{0.5,-0.5}};
int n,m;
ll _n,K;
double f[N],g[N];
void FWT(double *f,double c[2][2]){
for(int i=1;i<n;i<<=1)
for(int j=0;j<n;j+=i<<1)
for(int k=j;k<i+j;k++){
long long x=f[k],y=f[k+i];
f[k]=c[0][0]*x+c[0][1]*y;
f[k+i]=c[1][0]*x+c[1][1]*y;
}
}
int main(){
cin>>n>>m>>K;
rep(i,1,n){
char s[25];
cin>>s+1;
int w = 0;
rep(i,1,m) w=(w<<1)|(s[i]=='B');
f[w] += 1;
}
_n = n;
n = 1<<m;
FWT(f,Cxor);
rep(i,0,n-1) f[i] = f[i]*f[i];
FWT(f,ICxor);
//rep(i,0,n-1) cout<<f[i]<<" ";
rep(i,0,n-2) g[i] = f[(n-1)^i]/2;
g[n-1] = f[0] - _n;
//puts("");
//rep(i,0,n-1) cout<<g[i]<<" ";
//puts("");
FWT(g,Cand);
//rep(i,0,n-1) cout<<g[i]<<" ";
ll sum = 0;
rep(i,1,n-1) if(_n*(_n-1)/2-g[i]>=K) sum++;
cout<<sum;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3612kb
input:
2 2 1 AA BB
output:
3
result:
ok 1 number(s): "3"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
2 2 1 AA AB
output:
2
result:
ok 1 number(s): "2"
Test #3:
score: -100
Wrong Answer
time: 1ms
memory: 3556kb
input:
5000 10 12302135 AABAAAABBA AAABAABBAB BAABABAAAB ABBAABBBBA BAAAAABAAB BABBAAAAAA BABBABABAB BBABBAAAAB BABBABBBBA AAAAAAABAA BBBBBAABBA BAABABBAAB BABAAABAAA AAAAABAABB BBABAABABB ABAABBABBA BBBAAABABA BAAABABBAB ABAAAAABAA AABBBBBBAA ABBABBABBA AABBBABBAB BAABBAAABB BAAABBBBBB ABABBAABBB BABBABBA...
output:
176
result:
wrong answer 1st numbers differ - expected: '300', found: '176'