QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#124623 | #4327. Šeširi | He_Ren | 100 ✓ | 225ms | 149092kb | C++17 | 1.6kb | 2023-07-15 10:59:16 | 2023-07-15 10:59:17 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int ALL = (1<<19) + 5;
const int MAXE = ALL * 18;
#define bbit(i) (1<<(i))
#define bdig(x,i) (((x)>>(i))&1)
struct Edge
{
int next,to,res;
}e[MAXE];
int head[ALL], etot = -1;
inline void add_one(int u,int v)
{
e[++etot] = (Edge){ head[u],v,-1};
head[u] = etot;
}
inline void add_edge(int u,int v)
{
add_one(u,v); add_one(v,u);
}
int id[ALL][18];
int cur[ALL];
bool vis[ALL];
void dfs(int u)
{
vis[u] = 1;
for(int &i=cur[u]; ~i; i=e[i].next)
{
if(e[i].res != -1) continue;
int v = e[i].to;
e[i].res = 1;
e[i^1].res = 0;
dfs(v);
}
}
int main(void)
{
int n;
scanf("%d",&n);
int pcnt = (1<<n) * 2 + 1;
memset(head, -1, sizeof(head));
for(int i=0; i<(1<<n); ++i)
{
int cnt[2] = {0,0};
for(int k=0; k<n; ++k)
{
int x = bdig(i, k);
++cnt[x];
if(x == 1) continue;
int j = i ^ bbit(k);
id[i][k] = etot + 1;
add_edge(i << 1 | 0, j << 1 | 1);
}
if(cnt[0] & 1)
add_edge(i << 1 | 0, pcnt - 1);
if(cnt[1] & 1)
add_edge(i << 1 | 1, pcnt - 1);
}
memcpy(cur, head, sizeof(head));
for(int i=0; i<pcnt; ++i) if(!vis[i])
dfs(i);
static int ans[18][ALL];
for(int i=0; i<(1<<n); ++i)
for(int k=0; k<n; ++k) if(!bdig(i, k))
{
int mask = 0;
for(int kk=0; kk<n; ++kk) if(kk != k)
mask = mask << 1 | bdig(i, kk);
ans[k][mask] = e[id[i][k]].res;
}
for(int i=0; i<n; ++i, printf("\n"))
for(int j=0; j<(1<<(n-1)); ++j)
putchar(ans[i][j] + 'B');
return 0;
}
详细
Subtask #1:
score: 7
Accepted
Test #1:
score: 7
Accepted
time: 1ms
memory: 18928kb
input:
4
output:
BCBCCBCC CBCBBCBB BCBCCBCC CBCBBCBB
result:
ok good plan!
Subtask #2:
score: 7
Accepted
Test #2:
score: 7
Accepted
time: 0ms
memory: 20136kb
input:
5
output:
BBCCBBCCCBBBBBCB CCBBCBBBBCBCCCBC BBCBBBCCCBCBBBCB CCBCCCBCBCBBCCBC BBCBBBCBCBCCBBCB
result:
ok good plan!
Subtask #3:
score: 7
Accepted
Test #3:
score: 7
Accepted
time: 1ms
memory: 22372kb
input:
6
output:
BCBCCCBCBCBCCCCCCBCBBBBBCCBCCBCC CBCBBBCBCBCBBBBBBCBCCCCCBBCBBCBB BCBCCBCCBCBCCCCCCBCBBBBBCCBCCBCC CBCBBBCBCBCCBBCBBBCBCCBCBBCBBCBB BCBCCCBCBCBCCCBCCCBCBCCBCCBCCBCC CBCBBBCBCBCBBBCBBBCBCBBCBBCBBCBB
result:
ok good plan!
Subtask #4:
score: 7
Accepted
Test #4:
score: 7
Accepted
time: 0ms
memory: 25232kb
input:
7
output:
BBCCBCCBCBCCCBCCBBBCCCCBCCCCCBCCCBBBBBBBBBBBBBBBBBCBBBBCCBBBBBCB CCBBCBBCBBBBBCBBCBBBBBBBBBBBBBBBBCBCCCCCBCCCCCCCCCBBCBBBBCBCCCBC BBCCBBCBCBBCCBCBBBCCBCCCCCCBCBCCCBCBBBBBCBBBBBBBBBCCBCCCCBCBBBCB CCBBCBBCBCCBBCBCCCBCCBCBBCBCCCBBBCBBCCBCBBCCBCCCCCBBCBBBBCBCCCBC BBCBBCCBCBCCCBCBBBCBBBCCCBCBBBCCCBCCBBCB...
result:
ok good plan!
Subtask #5:
score: 7
Accepted
Test #5:
score: 7
Accepted
time: 1ms
memory: 26332kb
input:
8
output:
BCBCCCBCBCBCCCBCCBBBCBCCBCBBCCCCBBBCCCCCBCCBCCCCCCCCCCBCCCBCCCCCCBCBBBBBCBBCBBCBBBBBBBCBBBCBBBBBCCBCCBBCBBBCCCCCCBCBBBBBCCBCCBCC CBCBBBCBCBCBBBCBBBCCBCBBCBCCBBBBCBCBBBBBCBBCBBBBBBBBBBCBBBCBBBBBBCBCCCCCBCCBCCBCCCCCCCCCCCBCCCCCBBCBBBBBCBCBBBBBBCBCCCCCBBCBBCBB BCBCCCCCBCBCCCBCCBCBBBCBCCBCCBCCBCBCCCCCBC...
result:
ok good plan!
Subtask #6:
score: 7
Accepted
Test #6:
score: 7
Accepted
time: 1ms
memory: 28968kb
input:
9
output:
BBCCBCCBCCCCCBCCBBCBCBBCCBBCBCCCCBBCCCCBCCCCCBCBCBCCBCCBCBCCCBCCBBBCBCCBCCCBCBCCCCCCCBCCCBBCCCCBCCCCCBCBCBCCCBCCCBBCCCCBCCCCCBCCCBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBCBBBBBCBBBBBBBBBBBBBBBBBBBBCBBBBBCBBCBBCBBBBCBCCBBCCBCBBCCBBBBBBBBBBBBBBBBBCBBBBCCBBBBBCB CCBBCBBCBBBBBCBBCBBCBCCBBCCBCBBBBBBBBBBBBBB...
result:
ok good plan!
Subtask #7:
score: 7
Accepted
Test #7:
score: 7
Accepted
time: 1ms
memory: 31180kb
input:
10
output:
BCBCCCBCBCBCCCBCCCBBCBCCBCBBCCCCBCBCCCBCBCBBBCCCCCBCBCBCBCBCCCCCCBBBBBCBBBCBCBCBCBCCCCCBCCCBCBBCBCBBCCBCBCBCBCBBCBCBCBCCCCBCCCCCBBBCBCCBBCCBCBCCCCCCCCBCCCBCCCCCBCCBCCBCCCCCBCCBCBBCCCCCCCCCCCCCCCCCCCBCCCCCCCBCCBBBCBCCBCBBCCCCCBBCCCCCBCCBCCCCCCCCCCBCCCBCCCCCCBCBBBBBCBBCBBCBBBBBBBCBBBCBBBBBCBBCBBCBBBBB...
result:
ok good plan!
Subtask #8:
score: 7
Accepted
Test #8:
score: 7
Accepted
time: 0ms
memory: 33784kb
input:
11
output:
BBCCBCCBCCCCCBCCBCCBCBBCCBBCBCCBCBCCCCCCCCCCCCCCCBCCBCCBCCCCCBCCBBCBCBBBCBBCBBCCCBBCBCCCBBCCCCCCCBBCBCCCBCCCCCCCBBCCCCCCCCCCCCCCCBBCCCCBBCCBCBBBCCCCCBCBCBBBCBBBCCCCCBCBCBCBCBBCCBBBCBBBCBBCBBCBCBCCBCCBCBCCCBCCBBCBCBBCCBBCBCCCCBBCCCCBCCCCCBCBCBCCBCCBCBCCCBCCBBBCBCCBBCCBCBBCCCCBCBCCCBBCCCCBCCCCCBCCCBBC...
result:
ok good plan!
Subtask #9:
score: 7
Accepted
Test #9:
score: 7
Accepted
time: 1ms
memory: 37368kb
input:
12
output:
BCBCCCBCBCBCCCBCCCBBCBCCBCBBCCCCBCBCCCBCBCBBBCCCCCBCBCBCBCBCCCBCCBBBCBCCBBCBCCCBCBCCCCCBCCCBCBCCBCBBCCBCBCBCBCBBCCCBCBCCCCBCCCCCBBBCCCBCBCBBBCCCCCBCBCBCBCBCCCCCBCBBBCBCBCBCBCCBBBCCCCCCCCCCCCCCCCBCBCBCBCBCCCCCBCBBCBCCBCCBCCCCBCBCCCCCBCCBCCCCCCCCCCBCCCBCCCCCCBBBBBCBBBCBCBCBBBCBCBCBCBCBBBBBBBCBCCCBCCCB...
result:
ok good plan!
Subtask #10:
score: 7
Accepted
Test #10:
score: 7
Accepted
time: 2ms
memory: 40936kb
input:
13
output:
BBCCBCCBCCCCCBCCBCCBCBBCCBBCBCCBCCCCCCCCCCCCCCCCCBCCBCCBCCCCCBCCBBCBCBBCCBBCBCCBCBBCBCBBBCCBCBBCCBBCBCCBBCCBCBBCBCCBCBBCCBBCBCCCCBBCCCCBCCCCCBCCCCCCCCCCCBCCCCCCCCCCCCCCCCCCCCCCCBCCCCCCCCCCCCCBCBCCBCCBCCCCCBCCBCCBCBBCCBBCBCCBCBCCCCCCCCCCCCCCCBCCBCCBCCCCCBCCBBBBCBBBCBBCBBCCCBBCBBCCBBCCCCCBCBBCBCCCBBCC...
result:
ok good plan!
Subtask #11:
score: 6
Accepted
Test #11:
score: 6
Accepted
time: 5ms
memory: 43580kb
input:
14
output:
BCBCCCBCBCBCCCBCCCBBCBCCBCBBCCCCBCBCCCBCBCBBBCCCCCBCBCBCBCBCCCBCCCCBCBCCBBCBCCCBCBCCCCCBCCCBCBCCBCBBCCBCBCBCBCBBCCCBCBCCCCBCCCCCBCCCCCBCBCBBBCCCCCBCBCBCBCBCCCBCBCBBBCBCBBBCBCBBBCCCCCBCCCBCBCCCCCBCBCBCBCBCCCBCBCBBCBBCBCBBBCCCBCBCCCBCBCBBBCCCCCBCBCBCBCBCCCCCCBCBBBCBBBCBCBCBCBCCCCCBCCCBCBCCBBCBCCCBCCCB...
result:
ok good plan!
Subtask #12:
score: 6
Accepted
Test #12:
score: 6
Accepted
time: 20ms
memory: 52228kb
input:
15
output:
BBCCBCCBCCCCCBCCBCCBCBBCCBBCBCCBCCCCCCCCCCCCCCCCCBCCBCCBCCCCCBCCBCCBCBBCCBBCBCCBCBBCBCBBBCCBCBBCCBBCBCCBBCCBCBBCBCCBCBBCCBBCBCCBCBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCBCCBCCBCCCCCBCCBCCBCBBCCBBCBCCBCCCCCCCCCCCCCCCCCBCCBCCBCCCCCBCCBBCBCBBBCBBCBBCBCBBCBCCBBBCBCBBCCBBCBCCBBCCB...
result:
ok good plan!
Subtask #13:
score: 6
Accepted
Test #13:
score: 6
Accepted
time: 42ms
memory: 66632kb
input:
16
output:
BCBCCCBCBCBCCCBCCCBBCBCCBCBBCCCCBCBCCCBCBCBBBCCCCCBCBCBCBCBCCCBCCCCBCBCCBBCBCCCBCBCCCCCBCCCBCBCCBCBBCCBCBCBCBCBBCCCBCBCCCCBCCCCCBCCCCCBCBCBBBCCCCCBCBCBCBCBCCCBCBCBBBBBCBBBCBCBBBCCCCCBCCCBCBCCCCCBCBCBCBCBCCCBCBCBBCBBCBCBBBCCCBCBCCCBCBCBBBCCCCCBCBCBCBCBCCCBCCBCBCBCCCBCCCCCBCBCCCCCBCCCBCBCCBBCBCCCBCCCB...
result:
ok good plan!
Subtask #14:
score: 6
Accepted
Test #14:
score: 6
Accepted
time: 86ms
memory: 89604kb
input:
17
output:
BBCCBCCBCCCCCBCCBCCBCBBCCBBCBCCBCCCCCCCCCCCCCCCCCBCCBCCBCCCCCBCCBCCBCBBCCBBCBCCBCBBCBCBBBCCBCBBCCBBCBCCBBCCBCBBCBCCBCBBCCBBCBCCBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCBCCBCCBCCCCCBCCBCCBCBBCCBBCBCCBCCCCCCCCCCCCCCCCCBCCBCCBCCCCCBCCBBCBCBBCCBBCBCCBBBBCBCBBBCCBCBBCCBBCBCCBBCCB...
result:
ok good plan!
Subtask #15:
score: 6
Accepted
Test #15:
score: 6
Accepted
time: 225ms
memory: 149092kb
input:
18
output:
BCBCCCBCBCBCCCBCCCBBCBCCBCBBCCCCBCBCCCBCBCBBBCCCCCBCBCBCBCBCCCBCCCCBCBCCBBCBCCCBCBCCCCCBCCCBCBCCBCBBCCBCBCBCBCBBCCCBCBCCCCBCCCCCBCCCCCBCBCBBBCCCCCBCBCBCBCBCCCBCBCBBBBBCBBBCBCBBBCCCCCBCCCBCBCCCCCBCBCBCBCBCCCBCBCBBCBBCBCBBBCCCBCBCCCBCBCBBBCCCCCBCBCBCBCBCCCBCCCCBCBCCCBCCCCCBCBCCCCCBCCCBCBCCBBCBCCCBCCCB...
result:
ok good plan!
Extra Test:
score: 0
Extra Test Passed