QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#121165 | #4327. Šeširi | abs998244353 | 100 ✓ | 94ms | 68492kb | C++17 | 1.5kb | 2023-07-07 17:39:08 | 2023-07-07 17:39:10 |
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]){
int ii=cur[u];
cur[u]=nxt[cur[u]];
del[ii>>1]=1;
path(ver[ii]);
stk[++tp]=ii>>1;
}
else deg[u]^=1;
}
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;
}
}
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;
}
詳細信息
Subtask #1:
score: 7
Accepted
Test #1:
score: 7
Accepted
time: 3ms
memory: 15628kb
input:
4
output:
CCBBCCCC BBCCBBCC CCBBCCBB BBCBBBCB
result:
ok good plan!
Subtask #2:
score: 7
Accepted
Test #2:
score: 7
Accepted
time: 0ms
memory: 17656kb
input:
5
output:
CBCCBCCBCCCCCBCC BCBBCBCCBCBBCCBC CBCCBBCBCBCCBBCC BCBCCCBCBCBBCCBB CBCBBBCBCBCCBBCB
result:
ok good plan!
Subtask #3:
score: 7
Accepted
Test #3:
score: 7
Accepted
time: 0ms
memory: 19728kb
input:
6
output:
CCBCCCCCBBCCBBBBCCCCCCCBCCCCCCCC BBCBBBBBCCBCCBCCBBCBBBBBCCBCCBCC CCBBCCCCBBBBBCBCCCBBCCCCBBBBBCBC BBCCBBCBCBCCBBCBBBCCBBCBCBCCBBCB CCBBCCBCBCBBCCBBCCBBCCBCBCBBCCBB BBCBBBCBCBCCBBCBBBCBBBCBCBCCBBCB
result:
ok good plan!
Subtask #4:
score: 7
Accepted
Test #4:
score: 7
Accepted
time: 0ms
memory: 19724kb
input:
7
output:
CBCCBCCBCCCCCBCCBCCBCBBCCBBCCCCBCCCCCCCCCCCCBCCCCCBCCCCBBCCCCBCC BCBBCBBCBBBBBCBBCBCCBCCBCCCBBCCCBCBBCBBCBBBCCBBBCBCCBCCCCCCBCCBC CBCCBCCBCCCCCBCCBBCBBBBBCBBCCBCBCBCCBCCBCCCCBCBCBBCBCBBBBCBCCBCC BCBBCBCCBCBBCCBCCCBCCBCCBBCBBCBCBCBBCCBCBCBBCBCBCCBBBCCCCBBBBCBC CBCCBBCBCBCCBBCCBBCBBBCBCBCCCBCBCBCCBBCB...
result:
ok good plan!
Subtask #5:
score: 7
Accepted
Test #5:
score: 7
Accepted
time: 0ms
memory: 19648kb
input:
8
output:
CCBCCCCCBCCCCBBCCCCCCCCCCCCCCCCCBBCBBBBBCCBBCCCCBBBBBBBCBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCBCCBCCBCCCCCCCCCCCCCCCBCCCCCCCCCCCCCCCC BBCBBBBBCBBCBBCBBBBBBBBBBBBBBBBBCCBCCCCCBCCCCBBCCBCCBCCBCCCCCBCCBBCBBBBBCBBCBBCBBBBBBBBBBBBBBBBBCCBCCCCCBCCCCBBCCBCCBCCBCCCCCBCC CCBCCCCCBBCBBCBBCCCCCCCBCCCCCCCCBBBBBBBBBB...
result:
ok good plan!
Subtask #6:
score: 7
Accepted
Test #6:
score: 7
Accepted
time: 0ms
memory: 19720kb
input:
9
output:
CBCCBCCBCCCCCBCCBCCBCBBCCCCCBCCBCCCCCCCCCBBCCCCCCBCCBCCBCCCCCBCCBCCBCBBCCCCCBCCBCBBCBCCBBCCBCBBCCBBCBCCBBCCBCCBCCCCCCCCCCBBCCCCBCCCCCCCCCBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCBCCBCCBCBBCCCCCBCCCCCBCBCCCCCCBCCBCCCCCCCCCCBBCCCCBBCCBCBBCCCCCBCCCCCBCCCCBBCCCCBCC BCBBCBBCBBBBBCBBCBBCBCCBBBBBCBBCBBBBBBBBBCC...
result:
ok good plan!
Subtask #7:
score: 7
Accepted
Test #7:
score: 7
Accepted
time: 0ms
memory: 19644kb
input:
10
output:
CCBCCCCCBCCCCBBCCCCCCCCCCCCCCCCCBCCBCBBCCCBCCCCCCBBCBCCCBCCBCBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCBBCBBBBBCBBBBCCBBBBBBBBBBBBBBBBBCCBCCCCCBBCCBBBBCCCCCCCBCCCCCCCCBBBBBBBBBBBBBBBBBBBBBBBBBCBBCBBCBBBBBBBBBBBBBBBCBBBBBBBBBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC...
result:
ok good plan!
Subtask #8:
score: 7
Accepted
Test #8:
score: 7
Accepted
time: 0ms
memory: 19732kb
input:
11
output:
CBCCBCCBCCCCCBCCBCCBCBBCCCCCBCCBCCCCCCCCCBBCCCCCCBCCBCCBCCCCCBCCBCCBCBBCCCCCBCCBCBBCBCCBBCCBCBBCCCCCCCCCCCCCCBCCBCCBCCCCCCCCCCCBCCCCCCCCCBBCCCCCCCCCCCCCCCCCCCCCCBBCBCCBBCCBCCBCCCCCCBBCCBBCBCCCCBCCCCCBBCCCCBCCBCCBCCCCCCCCCCCBCCCCCBBCCBBCBCCCCBCCBCCBCCCCCBCCBCCBCBBCCCCCBCCBCBBCBCCBBCCBCBBCCCCCCCCCCCCC...
result:
ok good plan!
Subtask #9:
score: 7
Accepted
Test #9:
score: 7
Accepted
time: 0ms
memory: 21828kb
input:
12
output:
CCBCCCCCBCCCCBBCCCCCCCCCCCCCCCCCBCCBCBBCCCBCCCCCCBBCBCCCBCCBCBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCBCCBCBBCCBBCBCCBCBBCBCCBBCCBCBBCCCBCCCCCBCCCCBBCCCCCCCCCCCCCCCCCCBBCBCCBBCCBCBBCBCCBCBBCCCBCCCCCBCCBCBBCCBBCBCCCCBBCBCCBBCCBCBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC...
result:
ok good plan!
Subtask #10:
score: 7
Accepted
Test #10:
score: 7
Accepted
time: 0ms
memory: 24004kb
input:
13
output:
CBCCBCCBCCCCCBCCBCCBCBBCCCCCBCCBCCCCCCCCCBBCCCCCCBCCBCCBCCCCCBCCBCCBCBBCCCCCBCCBCBBCBCCBBCCBCBBCCCCCCCCCCCCCCBCCBCCBCCCCCCCCCCCBCCCCCCCCCBBCCCCCCCCCCCCCCCCCCCCCCBBCBCCBBCCBCCBCCCCCCBBCCBBCBCCCCBCCCCCBBCCCCBCCBCCBCCCCCBBCBCCBCCCCCBBCCCCCCCCCCBCCBCCBCCCCCBCCBCCBCBBCCCCCBCCBCBBCBCCBBCCBCBBCCCCCCCCCCCCC...
result:
ok good plan!
Subtask #11:
score: 6
Accepted
Test #11:
score: 6
Accepted
time: 7ms
memory: 23924kb
input:
14
output:
CCBCCCCCBCCCCBBCCCCCCCCCCCCCCCCCBCCBCBBCCCBCCCCCCBBCBCCCBCCBCBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCBCCBCBBCCBBCBCCBCBBCBCCBBCCBCBBCCCBCCCCCBCCCCBBCCCCCCCCCCCCCCCCCCBBCBCCBBCCBCBBCBCCBCBBCCCBCCCCCBCCBCBBCCBBCBCCCCBBCBCCBBCCBCBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC...
result:
ok good plan!
Subtask #12:
score: 6
Accepted
Test #12:
score: 6
Accepted
time: 9ms
memory: 26696kb
input:
15
output:
CBCCBCCBCCCCCBCCBCCBCBBCCCCCBCCBCCCCCCCCCBBCCCCCCBCCBCCBCCCCCBCCBCCBCBBCCCCCBCCBCBBCBCCBBCCBCBBCCCCCCCCCCCCCCBCCBCCBCCCCCCCCCCCBCCCCCCCCCBBCCCCCCCCCCCCCCCCCCCCCCBBCBCCBBCCBCCBCCCCCCBBCCBBCBCCCCBCCCCCBBCCCCBCCBCCBCCCCCCCCCCCBCCCCCBBCCBBCBCCCCBCCBCCBCCCCCBCCBCCBCBBCCCCCBCCBCBBCBCCBBCCBCBBCCCCCCCCCCCCC...
result:
ok good plan!
Subtask #13:
score: 6
Accepted
Test #13:
score: 6
Accepted
time: 13ms
memory: 32664kb
input:
16
output:
CCBCCCCCBCCCCBBCCCCCCCCCCCCCCCCCBCCBCBBCCCBCCCCCCBBCBCCCBCCBCBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCBCCBCBBCCBBCBCCBCBBCBCCBBCCBCBBCCCBCCCCCBCCCCBBCCCCCCCCCCCCCCCCCCBBCBCCBBCCBCBBCBCCBCBBCCCBCCCCCBCCBCBBCCBBCBCCCCBBCBCCBBCCBCBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC...
result:
ok good plan!
Subtask #14:
score: 6
Accepted
Test #14:
score: 6
Accepted
time: 58ms
memory: 47352kb
input:
17
output:
CBCCBCCBCCCCCBCCBCCBCBBCCCCCBCCBCCCCCCCCCBBCCCCCCBCCBCCBCCCCCBCCBCCBCBBCCCCCBCCBCBBCBCCBBCCBCBBCCCCCCCCCCCCCCBCCBCCBCCCCCCBCCCCBCCCCCCCCCBBCCCCCCCCCCCCCCCCCCCCCCBBCBCCBBCCBCCBCCCCCCBBCCBCCBCCCCBCCCCCBBCCCCBCCBCCBCCCCCCBCCCCBCCCCCBBCCBCCBCCCCCBCBCCBCCCCCBCCBCCBCBBCCCCCBCCBCBBCBCCBBCCBCBBCCCCCCCCCCCCC...
result:
ok good plan!
Subtask #15:
score: 6
Accepted
Test #15:
score: 6
Accepted
time: 94ms
memory: 68492kb
input:
18
output:
CCBCCCCCBCCCCBBCCCCCCCCCCCCCCCCCBCCBCBBCCCBCCCCCCBBCBCCCBCCBCBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCBCCBCBBCCBBCBCCBCBBCBCCBBCCBCBBCCCBCCCCCBCCCCBBCCCCCCCCCCCCCCCCCCBBCBCCBBCCBCBBCBCCBCBBCCCBCCCCCBCCBCBBCCBBCBCCCCBBCBCCBBCCBCBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC...
result:
ok good plan!
Extra Test:
score: 0
Extra Test Passed