QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #82595 | #2549. King's Palace | woxiangbaile# | WA | 109ms | 183908kb | C++ | 1.9kb | 2023-02-28 12:41:52 | 2023-02-28 12:41:55 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
const int mod=1e9+7;
#define inf 1e9
#define ll long long
inline int read(){
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
return x*f;
}
const int N=22;
int n,m,C[3][3][1<<N],all;ll ans,F[1<<N];
int main(){
n=read(),m=read();
int x,y,z1,z2;char c1,c2;
for(int i=1;i<=m;i++){
x=read(),c1=getchar(),y=read(),c2=getchar();
z1=(c1=='R'?0:(c1=='B'?1:2));--x;
z2=(c2=='R'?0:(c2=='B'?1:2));--y;
// printf("%d %d %d %d\n",x,z1,y,z2);
C[z1][z2][1<<x]|=(1<<y);
C[z2][z1][1<<y]|=(1<<x);
}all=(1<<n)-1;F[0]=1;
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
for(int S=1;S<=all;S++)
C[i][j][S]=C[i][j][S&(-S)]|C[i][j][S&(S-1)];
for(int S=1;S<=all;S++){
// if(!(C[2][2][S]&S))F[S]=1;
// for(int S1=S;S1;S1=(S1-1)&S)
// if(!(C[1][1][S1]&S1)&&!(C[1][2][S1]&(S^S1))&&!(C[2][2][S^S1]&(S^S1)))++F[S];
int S1=(S&-S),S2=0,S3=S&(S-1);
while(1){
int S4=C[1][2][S1]|C[2][2][S2];
int S5=C[1][1][S1]|C[2][1][S2];
S4&=S3,S5&=S3,S3^=S4^S5,S1|=S4,S2|=S5;
if(!S4&&!S5)break;if(S4&S5)break;
}//printf("S3=%d\n",S3);
if(!(S1&S2))F[S]+=F[S3];
S1=0,S2=(S&-S),S3=S&(S-1);
while(1){
int S4=C[1][2][S1]|C[2][2][S2];
int S5=C[1][1][S1]|C[2][1][S2];
S4&=S3,S5&=S3,S3^=S4^S5,S1|=S4,S2|=S5;
if(!S4&&!S5)break;if(S4&S5)break;
}//printf("S3=%d\n",S3);
if(!(S1&S2))F[S]+=F[S3];
// printf("F[%d]=%lld\n",S,F[S]);
}
for(int S=0;S<=all;S++){
if(C[0][0][S]&S)continue;
int S1=C[0][2][S],S2=C[0][1][S],S3=0;
S1=(S1&(all-S)),S2=(S2&(all-S)),S3=(all-S)^S1^S2;
if(S1&S2)continue;
while(1){
int S4=C[1][2][S1]|C[2][2][S2];
int S5=C[1][1][S1]|C[2][1][S2];
S4&=S3,S5&=S3,S3^=S4^S5,S1|=S4,S2|=S5;
if(!S4&&!S5)break;if(S4&S5)break;
}if(S1&S2)continue;
ans+=F[S3];
}printf("%lld\n",ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 9704kb
input:
2 3 1 R 2 R 1 G 2 R 1 B 2 G
output:
6
result:
ok answer is '6'
Test #2:
score: 0
Accepted
time: 2ms
memory: 3736kb
input:
1 0
output:
3
result:
ok answer is '3'
Test #3:
score: 0
Accepted
time: 79ms
memory: 183764kb
input:
22 0
output:
31381059609
result:
ok answer is '31381059609'
Test #4:
score: 0
Accepted
time: 2ms
memory: 3552kb
input:
4 12 2 R 3 R 1 B 2 B 2 R 3 B 3 R 4 R 1 B 4 G 1 R 3 B 3 G 4 B 2 G 3 G 1 B 2 R 1 G 2 R 1 R 3 G 1 G 3 B
output:
13
result:
ok answer is '13'
Test #5:
score: 0
Accepted
time: 2ms
memory: 3568kb
input:
2 4 1 G 2 G 1 B 2 R 1 R 2 G 1 B 2 B
output:
5
result:
ok answer is '5'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3548kb
input:
5 77 3 B 5 B 2 G 5 G 4 R 5 G 1 G 2 B 1 R 4 R 4 B 5 G 2 B 3 G 2 G 5 B 1 R 3 G 2 R 5 R 3 B 4 R 1 R 2 B 3 G 4 G 1 B 5 G 3 R 5 G 3 G 4 B 1 B 4 G 4 B 5 R 2 R 4 G 1 G 4 B 2 G 3 R 2 R 5 B 1 G 2 R 2 B 4 R 2 R 3 R 3 B 5 G 2 G 3 G 1 R 3 R 1 R 5 G 2 G 3 B 3 B 4 B 4 R 5 B 1 R 2 G 3 G 5 R 1 R 2 R 2 B 5 B 3 B 5 R...
output:
0
result:
ok answer is '0'
Test #7:
score: 0
Accepted
time: 2ms
memory: 3608kb
input:
10 141 3 B 9 B 1 R 8 R 4 B 8 R 2 B 4 R 2 R 7 B 6 B 9 R 1 R 9 R 4 R 8 G 3 B 8 R 3 B 5 G 4 B 9 B 4 G 5 R 2 R 3 G 7 B 8 G 5 B 7 R 7 B 8 R 2 B 8 B 7 R 10 B 2 G 10 G 6 G 8 B 1 R 4 B 8 R 10 B 2 G 3 B 2 B 5 B 3 R 4 R 3 B 7 R 3 R 7 R 2 R 10 R 3 G 9 G 5 B 10 G 6 R 8 B 3 R 9 G 1 B 10 G 3 R 8 G 1 B 3 R 4 R 9 R...
output:
0
result:
ok answer is '0'
Test #8:
score: 0
Accepted
time: 96ms
memory: 151052kb
input:
22 2079 1 R 2 R 1 R 2 G 1 R 2 B 1 G 2 R 1 G 2 G 1 G 2 B 1 B 2 R 1 B 2 G 1 B 2 B 1 R 3 R 1 R 3 G 1 R 3 B 1 G 3 R 1 G 3 G 1 G 3 B 1 B 3 R 1 B 3 G 1 B 3 B 1 R 4 R 1 R 4 G 1 R 4 B 1 G 4 R 1 G 4 G 1 G 4 B 1 B 4 R 1 B 4 G 1 B 4 B 1 R 5 R 1 R 5 G 1 R 5 B 1 G 5 R 1 G 5 G 1 G 5 B 1 B 5 R 1 B 5 G 1 B 5 B 1 R ...
output:
0
result:
ok answer is '0'
Test #9:
score: 0
Accepted
time: 1ms
memory: 13956kb
input:
4 52 1 G 2 B 2 G 4 R 1 G 4 B 1 G 3 G 3 B 4 B 2 R 4 B 2 G 3 G 3 B 4 R 1 B 2 B 1 G 4 G 3 G 4 B 1 B 4 R 3 R 4 G 2 B 4 B 1 G 2 G 3 G 4 G 2 R 3 R 1 R 3 G 2 R 4 G 2 B 3 B 2 B 3 G 2 R 3 G 1 B 3 G 1 G 4 R 1 G 2 R 2 G 4 B 1 G 3 R 1 R 2 R 1 R 2 G 1 R 4 G 2 R 4 R 2 B 3 R 1 B 3 B 2 B 4 R 3 R 4 R 2 G 4 G 3 B 4 G...
output:
0
result:
ok answer is '0'
Test #10:
score: 0
Accepted
time: 2ms
memory: 3488kb
input:
8 10 1 G 7 R 7 R 8 G 3 R 6 R 3 G 4 R 5 B 8 R 4 B 6 G 2 G 5 B 1 R 2 B 7 G 8 G 3 G 5 R
output:
1874
result:
ok answer is '1874'
Test #11:
score: 0
Accepted
time: 1ms
memory: 3548kb
input:
4 40 2 G 3 G 1 R 4 R 3 G 4 G 1 R 3 R 1 G 2 G 2 R 3 R 3 R 4 R 1 G 2 B 1 B 4 R 1 B 3 R 1 G 4 R 2 R 4 G 1 B 2 R 1 B 4 G 1 G 3 R 1 G 4 G 2 G 3 B 1 B 2 G 1 R 3 G 1 R 2 B 1 B 3 B 2 B 3 R 1 B 3 G 1 G 4 B 1 G 3 G 2 G 3 R 1 R 4 G 2 B 4 B 2 G 4 R 3 R 4 B 2 R 4 B 1 R 2 G 2 B 4 R 1 B 2 B 1 G 3 B 2 G 4 B 1 R 3 B...
output:
0
result:
ok answer is '0'
Test #12:
score: 0
Accepted
time: 2ms
memory: 3576kb
input:
2 3 1 B 2 B 1 R 2 R 1 G 2 R
output:
6
result:
ok answer is '6'
Test #13:
score: 0
Accepted
time: 1ms
memory: 3584kb
input:
3 24 1 R 2 B 1 B 3 B 2 G 3 B 1 B 2 G 1 B 2 B 2 R 3 G 1 G 3 B 2 B 3 R 1 R 3 R 2 R 3 R 1 B 3 R 1 B 3 G 1 R 3 B 2 R 3 B 2 B 3 B 1 R 2 R 2 G 3 G 2 B 3 G 1 G 2 G 1 G 3 G 1 G 2 R 2 G 3 R 1 G 2 B 1 R 3 G
output:
0
result:
ok answer is '0'
Test #14:
score: 0
Accepted
time: 2ms
memory: 3464kb
input:
9 176 2 G 3 R 1 G 4 R 4 B 5 G 5 G 7 B 8 G 9 R 1 R 4 B 4 B 8 B 1 B 5 B 6 B 8 B 2 G 6 G 2 B 8 B 1 R 9 B 2 B 8 G 1 G 4 G 1 B 3 R 3 R 7 B 7 B 8 B 5 B 6 R 6 R 9 R 5 R 7 G 4 G 9 B 3 G 9 G 1 R 6 R 1 G 3 G 3 R 6 R 4 G 5 R 4 G 7 B 2 G 8 B 1 B 9 R 3 G 8 R 3 R 5 G 5 R 9 R 3 G 5 R 1 R 4 R 4 B 7 B 3 R 9 R 2 B 4 ...
output:
0
result:
ok answer is '0'
Test #15:
score: -100
Wrong Answer
time: 109ms
memory: 183908kb
input:
22 38 12 G 17 B 1 G 20 R 9 B 20 G 15 G 19 B 11 B 22 R 13 R 19 G 21 R 22 B 4 G 11 B 9 R 10 R 8 R 15 B 1 G 16 B 13 R 19 B 1 G 11 G 9 R 11 G 7 B 8 G 9 R 18 G 3 G 13 B 3 G 14 B 10 R 16 R 14 G 16 B 3 R 9 R 18 R 21 B 11 B 20 G 1 G 10 G 2 R 16 G 6 B 20 R 4 B 20 B 8 G 10 B 7 R 11 R 16 G 18 G 3 B 8 B 11 R 22...
output:
274252314
result:
wrong answer expected '258518109', found '274252314'