QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #61374 | #1083. Belarusian State University | grass8cow | WA | 3ms | 7828kb | C++14 | 1.7kb | 2022-11-12 18:21:57 | 2022-11-12 18:21:58 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,c[18][2][2],A[18],T[18],B[18];
char S[4];
void sw(ll *a,int i,int ty){
if(ty==0)for(int p=0;p<(1<<n);p++)if((p>>i)&1)a[p^(1<<i)]+=a[p],a[p]=0;
if(ty==1)for(int p=0;p<(1<<n);p++)if((p>>i)&1)a[p]+=a[p^(1<<i)],a[p^(1<<i)]=0;
if(ty==2)for(int p=0;p<(1<<n);p++)if((p>>i)&1)swap(a[p],a[p^(1<<i)]);
}
ll a[1<<18],b[1<<18],ans[1<<18];
void FWT(ll *a,int fl){
for(int w=0;w<n;w++){
int o=(1<<(fl?w:(n-1-w)));
for(int i=0;i<(1<<n);i+=(o<<1))for(int j=0;j<o;j++){
if(!T[w]){
if(fl)a[i+j]+=a[i+j+o];
else a[i+j]-=a[i+j+o];
}
else{
ll x=a[i+j],y=a[i+j+o];
a[i+j]=x+y,a[i+j+o]=x-y;
if(!fl)a[i+j]/=2,a[i+j+o]/=2;
}
}
}
}
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%s",S);
for(int j=0;j<2;j++)for(int k=0;k<2;k++)c[i][j][k]=S[2*j+k]-'0',A[i]+=c[i][j][k];
}
for(int i=0;i<(1<<n);i++)scanf("%lld",&a[i]);
for(int i=0;i<(1<<n);i++)scanf("%lld",&b[i]);
for(int i=0;i<n;i++){
if(A[i]==4)sw(a,i,1),sw(b,i,1);
else if(A[i]==0)sw(a,i,0),sw(b,i,0);
else if(A[i]==1||A[i]==3){
for(int j=0;j<2;j++)for(int k=0;k<2;k++)if(c[i][j][k]&&A[i]==1||!c[i][j][k]&&A[i]==3){
if(!j)sw(a,i,2);
if(!k)sw(b,i,2);
}
if(A[i]==3)B[i]=1;
}
else{
if(c[i][1][0]&&c[i][0][1]){T[i]=1;continue;}
if(c[i][0][0]&&c[i][1][1]){T[i]=B[i]=1;continue;}
if(c[i][1][0]==c[i][1][1]){
sw(b,i,1);
if(!c[i][1][0])B[i]=1;
}
if(c[i][0][1]==c[i][1][1]){
sw(a,i,1);
if(!c[i][0][1])B[i]=1;
}
}
}
FWT(a,1),FWT(b,1);
for(int i=0;i<(1<<n);i++)ans[i]=a[i]*b[i];
FWT(ans,0);
for(int i=0;i<n;i++)if(B[i])sw(ans,i,2);
for(int i=0;i<(1<<n);i++)printf("%lld ",ans[i]);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 7828kb
input:
3 0111 0110 0001 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0
output:
0 0 0 0 0 0 0 1
result:
ok 8 numbers
Test #2:
score: 0
Accepted
time: 3ms
memory: 7612kb
input:
2 1100 1101 2 0 2 1 2 0 2 1
output:
2 4 3 16
result:
ok 4 number(s): "2 4 3 16"
Test #3:
score: 0
Accepted
time: 0ms
memory: 7752kb
input:
1 0000 142857142 857142857 998244353 1755646
output:
999999998000000001 0
result:
ok 2 number(s): "999999998000000001 0"
Test #4:
score: 0
Accepted
time: 3ms
memory: 7640kb
input:
8 0000 0001 0010 0011 0101 1011 1101 1111 92726 51723 30325 31984 47551 61529 94856 58867 99699 44383 29317 34253 85206 99155 54057 21538 23635 64524 11223 78186 73723 38530 99909 38218 32839 92947 57594 79376 87975 25597 26783 11600 77813 98155 26224 76035 42536 80097 32406 81442 49449 76444 40502 ...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2008949968122 0 631347707836 0 560922365664 ...
result:
ok 256 numbers
Test #5:
score: -100
Wrong Answer
time: 3ms
memory: 7772kb
input:
9 1011 1011 0111 0110 1000 0000 0001 0100 1011 3 1 3 6 0 3 0 0 2 9 4 4 3 0 4 0 3 2 3 0 0 4 0 0 3 4 0 6 2 2 4 5 0 2 3 3 2 4 4 0 3 1 3 5 3 0 4 4 0 0 5 0 2 1 2 0 3 4 0 4 0 8 3 3 0 4 5 0 2 2 3 4 3 1 1 5 7 0 0 0 2 3 0 2 3 5 0 0 0 4 0 0 2 4 3 2 2 6 0 3 5 2 4 7 5 0 2 5 5 0 6 2 3 0 0 5 1 4 5 8 4 2 3 7 0 4 5...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
wrong answer 262nd numbers differ - expected: '1526976', found: '1241632'