QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#329942#6611. United in StormwindOgiso_SetsunaWA 1ms3624kbC++141.1kb2024-02-17 09:48:222024-02-17 09:48:24

Judging History

你现在查看的是最新测评结果

  • [2024-02-17 09:48:24]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3624kb
  • [2024-02-17 09:48:22]
  • 提交

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-1) g[i] = f[(n-1)^i];
	//puts("");

	FWT(g,Cand);
	//rep(i,0,n-1) cout<<g[i]<<" ";
	ll sum = 0;
	rep(i,1,n-1) if(_n*_n-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: 3488kb

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: 3624kb

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:

1023

result:

wrong answer 1st numbers differ - expected: '300', found: '1023'