QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#121149 | #4327. Šeširi | abs998244353 | 0 | 204ms | 66192kb | C++17 | 1.6kb | 2023-07-07 17:13:00 | 2023-07-07 17:13:01 |
Judging History
answer
#include <cstdio>
using namespace std;
int read(){
char c=getchar();int x=0;
while(c<48||c>57) c=getchar();
do x=(x<<1)+(x<<3)+(c^48),c=getchar();
while(c>=48&&c<=57);
return x;
}
const int N=(1<<19)|3,M=5000003;
int hd[N],ver[M],nxt[M],tot=1;
int cur[N];
bool del[M];
int n;
int stk[M],tp;
bool deg[N];
void add(int u,int v){
deg[v]^=1;
nxt[++tot]=hd[u];hd[u]=tot;ver[tot]=v;
}
void path(int u){
while(cur[u]&&del[cur[u]>>1]) cur[u]=nxt[cur[u]];
if(cur[u]){
del[cur[u]>>1]=1;
path(ver[cur[u]]);
stk[++tp]=cur[u]>>1;
cur[u]=nxt[cur[u]];
}
else deg[u]^=1;
//printf("%d ",u);
}
void dfs(int u){
for(int i=cur[u];i;i=cur[u]){
cur[u]=nxt[i];
if(del[i>>1]) continue;
del[i>>1]=1;
dfs(ver[i]);
stk[++tp]=i>>1;
}
//printf("%d ",u);
}
int id[18][1<<17];
bool res[M];
int que[N],tl;
int main(){
n=read();
for(int i=0;i<n;++i)
for(int s=0;s<(1<<(n-1));++s){
int msk=s&((1<<(n-i-1))-1);
int u=((s^msk)<<1)|msk;
int v=u|(1<<(n-i-1))|(1<<n);
add(u,v);add(v,u);
id[i][s]=tot>>1;
}
for(int i=0;i<(1<<(n+1));++i){
cur[i]=hd[i];
if(deg[i]) que[++tl]=i;
}
for(int pos=1;pos<=tl;++pos){
int u=que[pos];
if(deg[u]){
deg[u]^=1;
path(u);
int par=(u>=(1<<n));
while(tp){
res[stk[tp--]]=par;
par^=1;
}
}
}
for(int i=0;i<(1<<(n+1));++i){
dfs(i);
int par=(i>=(1<<n));
while(tp){
res[stk[tp--]]=par;
par^=1;
}
}
for(int i=0;i<n;++i){
for(int s=0;s<(1<<(n-1));++s)
if(res[id[i][s]]) putchar('C');
else putchar('B');
putchar('\n');
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 15620kb
input:
4
output:
BBCCBBBB CCBBCCBB BBCCBBBC CCBCCCBC
result:
wrong answer your plan fails on CCCB
Subtask #2:
score: 0
Wrong Answer
Test #2:
score: 0
Wrong Answer
time: 0ms
memory: 17688kb
input:
5
output:
BCBBCBBCBBBBBCBB CBCCBCBBCBCCBBCB BCBBCCBCBCBBCCBB CBCBBBBBCBBCBBCC BCBCCCBCBCBBCCBC
result:
wrong answer your plan fails on CCCCB
Subtask #3:
score: 0
Wrong Answer
Test #3:
score: 0
Wrong Answer
time: 0ms
memory: 19704kb
input:
6
output:
BBCBBBBBCCBBCCCCBBBCBBBCBBBBBBBB CCBCCCCCBBCBBCCBCCBCCCCCBBCBBCBB BBCCBBBCCCCCCBCBBBCCBBBBBCCCCBBB CCBBCCBCBCBBCBBCCCBBCCBBBCBBCBBC BBCCBBBBCBCBBBBCBBCCBBBBBBCCBBBC CCBCCCBBBBBBCBBCCBBCCCBCBBBBCCBC
result:
wrong answer your plan fails on CCCBBB
Subtask #4:
score: 0
Wrong Answer
Test #4:
score: 0
Wrong Answer
time: 0ms
memory: 19640kb
input:
7
output:
BCBBCBBCBBBBBCBBCBBCBCCBBCCBBBBCBBCBBBBBBBBBCBBBBBCBBBBCCBBBBCBB CBCCBCCBCCCCCBCCBCBBCBBCBBBCCBBBCBCCBCCBCCCBBCCCBCBBCBBBBBBCBBCB BCBBCBBCBBBBBCBBCBBCCCCCBCCBBCBCBBBBCBBCBBBBCBCBCCBCBCCCCBCBBCBB CBCCBCBBCBCCBBCBBBCBBCBBBCBCCBBBCBCCBBCBBBCCBBBCBBCCCBBBBCCCCBCB BCBBCCBCBCBBCCBBCCBCCCBCBCBBBBBCBCBBCCBC...
result:
wrong answer your plan fails on CCCCBBB
Subtask #5:
score: 0
Wrong Answer
Test #5:
score: 0
Wrong Answer
time: 0ms
memory: 17672kb
input:
8
output:
BBCBBBBBCBBCBBCBBBBCBBBBBBBBBBBBCCBCCCCCBBCCBBBCCCCCCCCBCCCCCCCCBBBCBBBBBCBBCBBCBBBBBBBBBCBBCBBBBBBBBBBBBBBBBBBCBBBBBBBCBBBBBBBB CCBCCCCCBCCBCCCCCCCCCCCCCCCCCCCCBBCCBBBBCBBBBCCBBCCBCBBCCBBCBCCBCCBCCCCCBCCBCCBCCCCCCCCBCCCCCBCCBBCBBBBBCBBBBCBBBCBBCBBCBBBCBCBB BBCBBBBCCCBCCBCCBBBCBBBCBCBBCBBCCCCCCCCCCC...
result:
wrong answer your plan fails on CCCBBBBB
Subtask #6:
score: 0
Wrong Answer
Test #6:
score: 0
Wrong Answer
time: 0ms
memory: 19708kb
input:
9
output:
BCBBCBBCBBBBBCBBCBBCBCCBBBBBCCBCBBBBBBBBBCCBBBCBBCBBCBBCBBBBBCBBCBBCBCCBBBBBCBBCBCCBCBBCCBBCBCCBBCCBCBBCCBBCBBCBBBBBBBBBBCCBBBBCBCCBBBBBCCCCBBCBBBBBBBBBBBBBBBBBBBBCBBBBBBBBBCBBCBBCBCCBBBBBCBBBBBCBCBBBBBBCBBCCBBBBBBBBBCCBBBBCCBBCBCCBBBBBCBBBBBCBBBBCCBBBBCBB CBCCBCCBCCCCCBCCBCCBCBBCCCCCBBCBCCBCCCCCCBB...
result:
wrong answer your plan fails on CCCCBBBBB
Subtask #7:
score: 0
Wrong Answer
Test #7:
score: 0
Wrong Answer
time: 0ms
memory: 19748kb
input:
10
output:
BBCBBBBBCBBCBCCBBBBCBBBBBBBBBBBBCBBCBCCBBCCBCBBCBBCBBBBCCBBCBCCBBBBCBBBBBCBBCBBCBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBCBBBBBBBBCCBBCCCCBCCCCBBBCCCCCCCBCCCCCBCCBBCBBBBBCCBCCBBCBBBBBBBCBCBBCBBCCCCCCCCCCCCCCCCBCCCBCCCCCBCCBCCBCCCCCCCCCCCCCCCBCCCCCCCBCCCCCBCCBBBCBBBBBCBBCBBCBBBBBBBBBBBBBCBBBCBBCBBCBBBC...
result:
wrong answer your plan fails on CCCBBBBBBB
Subtask #8:
score: 0
Wrong Answer
Test #8:
score: 0
Wrong Answer
time: 0ms
memory: 21832kb
input:
11
output:
BCBBCBBCBBBBBCBBCBBCBCCBBBBBCCBCBBBBBBBBBCCBBBCBBCBBCBBCBBBBBCBCCBBCBCCBBBBBCCBCBCCBCBBCCBBCBCCBBBBBBBBBBBBBBCBBCBBCCBBBBBBBBBBCBBBBBBBBBCCBBBCBBBBBBBBBBBBBBBBBBCCBCBBCCBBCBBCBBBBBBCCBCCCBCBBBBCBBBBBCCBBBBCBCCBBCBBBBBBBBBBBCBBBBBCCBBCCBCBBBBCBBCBBCBBCBBCBBCBBCBCCBBBBBCBBCBCCBCBBCCBBCBCCBBBBBBBBBBBBB...
result:
wrong answer your plan fails on CCCCBBBBBBB
Subtask #9:
score: 0
Wrong Answer
Test #9:
score: 0
Wrong Answer
time: 2ms
memory: 19684kb
input:
12
output:
BBCBBBBBCBBCBCCBBBBCBBBBBBBBBBBBCBBCBCCBBCCBCBBCBCCBCBBCCBBCBCCBBBBCBBBBBCBBCBBCBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBCBBBBBBBBCBBCBCCBBCCBCBBCBCCBCBBBCBBCBBCBBCCBCBBCCBBCBCBBCBBCBCCBBCCBCBBCBBCBBBBBCBBCBBCCBBBBBBBBBCBBCBBCCBBCBCCBBCCBCBBCBCCBCBBBCBBCBBCBBBBCBBBBBCBBCBBCBBBBBBBCBBBBBBBBBCBBCBBCBBBC...
result:
wrong answer your plan fails on CCCBBBBBBBBB
Subtask #10:
score: 0
Wrong Answer
Test #10:
score: 0
Wrong Answer
time: 5ms
memory: 21924kb
input:
13
output:
BCBBCBBCBBBBBCBBCBBCBCCCBBBBCBBCBBBBBBBBBCCCBBBBBCBBCBBCBBBBBCBBCBBCBCCCBBBBCBBCBCCBCBCCCBBCBCCCBBBBBBBBBBBBBCBBCCBCCBBBBBBBBBBCBBBBBBBBBCCCBBCBBBBBBBBBBBBBBBBBBCCBCBCCCBBCBBCCBBCBBCCBCCCBCBBBBCBBBBBCCBBBBCBBCBBCBBBCBCCBCBCCBBBBBCCBBBBBBCBBBCBCCBBCBCBBCCBCCBBCBCCCBBBBCBBCBCCBCBCCCBBCBCCCBBBBBBBBBBBB...
result:
wrong answer your plan fails on CCCCCCBBBBBBB
Subtask #11:
score: 0
Wrong Answer
Test #11:
score: 0
Wrong Answer
time: 4ms
memory: 23976kb
input:
14
output:
BBCBBBBBCBBCBCCBBBBCBBBBBBBBBBBBCBBCBCCBBCCBCBBCBCCBCBBCCBBCBCCBBBBCBBBBBCBBCBBCBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBCBBBBBBBBCBBCBCCBBCCBCBBCBCCBCBBBCBBCBBCBBCCBCBBCCBBCBCBBCBBCBCCBBCCBCBBCBCCBCBBCCBBCBCCBCBBCBCCCBCCBCCCCCBBCBCCCBCCBCBBCBCCBCBBCCBBCBCCBBBBCBBBBBCBBCBBCBBBBBBBCBBBBBBBBBCBBCBBCBBBC...
result:
wrong answer your plan fails on CCCBBBBBBBBBBB
Subtask #12:
score: 0
Wrong Answer
Test #12:
score: 0
Wrong Answer
time: 8ms
memory: 26724kb
input:
15
output:
BCBBCBBCBBBBBCBBCBBCBCCBBBBBCBBCBBBBBBBBBCCBBBBBBCBBCBBCBBCBBCBBCBBCBCCBBBBBCBBCBCCCCBBCCBBCCCCBBBBBBBBBBBCBBCBBCCBCBBBBBBBBBBBCBBBBBBBBBCCBBBCBBBBBBBBBBBCBBBBBBCCCCBBCCBBCCBCBBBCBBCCBBCCBCBBBBCBBBBBCCBBBBCBBCBBCBBBCBBBBBBBCBBBBBCCBBCCBCCCBBCBBCBBCBBBBBCBBCBBCBCCBBBBBCBBCBCCCCBBCCBBCCCCBBBBBBBBBBBCB...
result:
wrong answer your plan fails on CCCBBBBBBBBBBBB
Subtask #13:
score: 0
Wrong Answer
Test #13:
score: 0
Wrong Answer
time: 23ms
memory: 33116kb
input:
16
output:
BBCBBBBBCBBCBCCBBBBCBBBBBBBBBBBBCBBCBCCBBCCBCBBCBCCBCBBCCBBCBCCBBBBCBBBBBCBBCBBCBBBBBBBBBBBBBBBCBBBBBBBBBBBBBBBCBBBBBBBCBBBCBCCBCBBCBCCBBCCBCBBCBCCBCBBBCBBCBBCBBCCBCBBCCBBCBCBCCBBCBCCCBCCCCCCCBCCBCBBCCBBCBCCBCBBCBCCBBCCBCBBCCBBCBCCBBCCBCBBCBCCBCBBCCBBCBCCBBBBCBBBBBCBBCBBCBBBBBBBCBBBBBBBCBCBBCBBCBBBC...
result:
wrong answer your plan fails on CCCBBBBBBBBBBBBB
Subtask #14:
score: 0
Wrong Answer
Test #14:
score: 0
Wrong Answer
time: 70ms
memory: 46044kb
input:
17
output:
BCBBCBBCBBBBBCBCCBBCBCCCBBBCCBBCBBBBBBBCBCCCBBBBBCBBCBBCBBBBBCBBCBBCBCCCBBBCCBBCBCCCCBBCCBBCBCCBBBBBBBBBBBBBBCBBCCBCBBBCBBCCBCCCBBBBBBBCBCCCBBCBBBBBBBBBBBBBBBBBBCCCCBBCCBBCBBCCBBCBBCCCBCBCCCCBBCBBBBBCCBBBBCBBCBBCBBBCBBCBBCBCBCBBBCCBBCBBCBCBBBCBCCBCBBBBBCBBCBBCBCCCBBBCCBBCBCCBCBBCCBBCBCCBBBBBBBBBBBBB...
result:
wrong answer your plan fails on CCCCCBBBBBBBBBBBB
Subtask #15:
score: 0
Wrong Answer
Test #15:
score: 0
Wrong Answer
time: 204ms
memory: 66192kb
input:
18
output:
BBCBBBBBCBBCBCCBBBBCBBBBBBBBBBBBCBBCBCCBBCCBCBBCBCCBCBBCCBBCBCCCBBBCBBBBBCBBCBBCBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBCBBBBBBBCBBBCBCCBCBBCBCCBBCCBCBBCBCCBCBBBCBBCBBCCBCCBCBBCCBBCBCBCCBBCBCCCBCCCCCCCBCCBCBBCCBBCBCCBCBBCBCCBBCCBCBBCCBBCBCCBBCCBCBBCBCCBCBBCCCBCBCCBBBBCBBBBBCBBCBBCBBBBBBBCBBBBBBBCBCBBCBBCBBBC...
result:
wrong answer your plan fails on CCCBBBBBBBBBBBBBBB