QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#526775 | #4327. Šeširi | December456 | 94 | 1100ms | 174936kb | C++14 | 2.0kb | 2024-08-21 20:12:19 | 2024-08-21 20:12:20 |
Judging History
answer
#include <cstdio>
#include <algorithm>
constexpr int MAXN = 18;
constexpr int MAXV = 1 << MAXN;
constexpr int MAXM = (MAXN + 1) * MAXV >> 1 | 1;
class Edge {
public:
int v, nxt;
} e[MAXM << 1];
int eCnt = 1, len = 0, h[MAXV], cur[MAXV], euler[MAXM], id[MAXV];
bool vis[MAXM << 1];
char ans[MAXN][MAXV];
void addEdge(int u, int v) {
e[++ eCnt] = {v, h[u]};
h[u] = eCnt;
e[++ eCnt] = {u, h[v]};
h[v] = eCnt;
}
void solve(int u) {
for (int &i = cur[u]; i;) {
int v = e[i].v, j = i;
i = e[i].nxt;
if (!vis[j]) {
vis[j] = vis[j ^ 1] = true;
solve(v);
}
}
euler[len ++] = u;
}
int main() {
int n;
scanf("%d", &n);
for (int st = 0; st < 1 << n; st ++) {
for (int i = 0; i < n; i ++) {
if (!(st >> i & 1)) {
addEdge(st, (st ^ 1 << i) | 1 << n);
}
}
}
int all = (1 << n) - 1;
for (int st = 0; st < 1 << n; st ++) {
if (__builtin_popcount(all ^ st) & 1) {
addEdge(st, (all ^ st) | 1 << n);
}
}
for (int i = 0; i < n; i ++) {
id[1 << i] = i;
}
for (int st = 0; st < 1 << (n + 1); st ++) {
cur[st] = h[st];
}
for (int st = 0; st < 1 << (n + 1); st ++) {
if (!cur[st]) {
continue;
}
len = 0;
solve(st);
for (int i = 1; i < len; i ++) {
int st = (euler[i] ^ euler[i - 1]) & all;
if (st == all) {
continue;
}
int u = id[st], tmp = (1 << u) - 1, ed = euler[i];
ans[u][(all >> 1) ^ ((ed & all) >> (u + 1) << u | (ed & tmp))] = 'B' ^ (bool){ed >> n};
}
}
std::reverse(ans, ans + n);
for (int i = 0; i < n; i ++) {
std::reverse(ans[i], ans[i] + (1 << (n - 1)));
printf("%s\n", ans[i]);
}
return 0;
}
详细
Subtask #1:
score: 7
Accepted
Test #1:
score: 7
Accepted
time: 0ms
memory: 8728kb
input:
4
output:
BCBBBCBB BBCCCBCB CCBBCCCC CBCCBBBC
result:
ok good plan!
Subtask #2:
score: 7
Accepted
Test #2:
score: 7
Accepted
time: 1ms
memory: 9948kb
input:
5
output:
BBCCBBBBCBBCBBCB BCBBCCCCBCCBCCBB CBCCBBBBCCBCCCBC CCBBCCCCBBCBBBCC CBCCBCCBCCBCCCBC
result:
ok good plan!
Subtask #3:
score: 7
Accepted
Test #3:
score: 7
Accepted
time: 2ms
memory: 9264kb
input:
6
output:
BCBBBCBBBBBBBBBCCCBBBBCBBBCBBCBB BBCCBBCBCCBCBBCBBBBBBCBCCBBCCBBB BCBBCCBCBBCBCCBCCCCCCBCBBCCCBBCB CBCCBBCBCCBCBCBCCBCBBCCBCBBBCCCC CCBBCCCCBBBBCBCBCCBCBBBCCCCCBBCC CBCCBCCBCCCCCCBCBBCCCCCCBCCBCBBC
result:
ok good plan!
Subtask #4:
score: 7
Accepted
Test #4:
score: 7
Accepted
time: 0ms
memory: 8260kb
input:
7
output:
BBCCBBCBCBBCBBCBBBBBBCBBBBBBBBBBCBCCBBCBBCCBCBBCBBCBBCBBCCBCCBCB BCBBCCBCBBCBCCBCCCCCBBCBBCCBCCBCBBBBBCBBBBBCBCBBCCBBCBCCBBCBBCBB BBCCBBCBCCBCBBCBBBBBCCBCCBBCBBBBCBCCBBCBCCCCCCBCBBCCBCBCCBBBCCBB CCBBCCBCBBCBCCBCCCBCBBCBBCBCCBCCBCCBCCBCBBCBBBCBCCBBCBCBBCCCBBCC CBCCBBCBCCBCCCBCBBCBBCBBCCBBBCCBCCBCBCBB...
result:
ok good plan!
Subtask #5:
score: 7
Accepted
Test #5:
score: 7
Accepted
time: 0ms
memory: 8920kb
input:
8
output:
BCBBBCBCBBBBBBBBBCBBBBBCBBBCBBBBCBBBBBBCBBBBBCBBBBBCCCBBCCBBBBBCCCBBBBCBBBBCCBBBBBBBCBBBCBBBBBBBBBCBCCBBCBBBBBCBCCBBBBCCCBCBBCBB BBCCBBCBCCBCBBCCBBCBBCBBBBBBBCCCCCBCBBCBBCCCCBBBBBCBBBBBCBCCBBCBBBBBBCBCCBCBBCBBBBCCBCBBBCBBBBCCCCBCBBBBBCBBCBBCBBBBCCBBBCBCCBBB BCBBCCBCBBCBCCBCCCBCBBCBBCCBCCBBBBCBBCBCBB...
result:
ok good plan!
Subtask #6:
score: 7
Accepted
Test #6:
score: 7
Accepted
time: 3ms
memory: 11360kb
input:
9
output:
BBCCBBCBCBBCBBCCBBBBBCBBBBBBBBCBCBCCBBCBBCCBCBBCBBCBBBBBCBBCBBCBBBBBBCBBBBBBBBBBBCBBCBCCBBBBBCBBBBBBBBBBBBBBBBBBBCBBBBBBBBBBBBBBCBCCBBCBBCCBCBCCBBCBBBBBCBBCBBCBBCCBCBBCCBBCBCCBCCBCBCCBBCCBCBBCBBCBBBCBCCCCBBCBBCBBBBBBBBBBBBBBCCBCBCCBBCCBCCBCCBCBBCBBCCBCCBCB BCBBCCBCBBCBCCBBCCCCBBCCBCCBCCBCBBBBCCBBBBB...
result:
ok good plan!
Subtask #7:
score: 7
Accepted
Test #7:
score: 7
Accepted
time: 0ms
memory: 13664kb
input:
10
output:
BCBBBCBCBBBBBBBBBCBBBBBCBBBBBCBBBBBBBBBBBBBCBBBBBBBBBBBBBBBBBBBCCCBBBBBCBBBBBCBBBBBCBCBBBCBBBBBBBBBBBCBBCBBBBBBBCCBBBBBCBBBBBCBBCBBBBBBBBBBCBBBBBBBBBBBBCBBBBBBBBBBCCBBBCCBBBBBCCBBBBBBBBBBCBBBBBBBBCBBBCBBBBBBBCBBBBBBBBBBBCBBBCBBBBBBBBBBBCBBBBBCBBBBBCBBBBBBCCCBBBBCCBBBBCCBBBBBCCCBBCCBBBBBCBBBBCCBBCBBB...
result:
ok good plan!
Subtask #8:
score: 7
Accepted
Test #8:
score: 7
Accepted
time: 3ms
memory: 8976kb
input:
11
output:
BBCCBBCBCBBCBBCCBBCBBCBBBBBBBBCBCBBCBBCBBCCBCBBCBBCBBBBBCBBCBBCBBBBBBCBBBBBBBBBBBCBBCBCCBCBBBCBBBBBBBBBBBCBBBBBBBBBBBBBBBBBBBBBBCBCCBBCBBCCBCBCCBBCBBCBBCCBCBBCBBCCBCBBCCCBCBCCBCBBCBCCBBCCBCBCCBBCBBCBBCCCCBBCBBBBBBBBBBBBBBBBBCBBCBCCBBCCBCBCCBBCBBBCBCBBCBBCBBBBBBCBBBBBBBBBBBCBBCCCCBBBBBCBBBBBBBBBBBBBB...
result:
ok good plan!
Subtask #9:
score: 7
Accepted
Test #9:
score: 7
Accepted
time: 0ms
memory: 9248kb
input:
12
output:
BCBBBCBCBBBBBBBBBCBBBBBCBBBBBCBCBBBBBBBBBBBCBBBBBBBBBBBBBBBBBBBCBCBBBBBCBBBBBCBBBBBCBCBBBCBBBBBBBBBBBCBBBBBBBBBBBCBBBBBCBBBBBCBBCBBBBBBBBBBCBBBBBBBBBBBBBBBBBBBCBBBCBBBBBCBBBBBBBBBBBBBBBBBCBBBBBBBBBBBBBBBBBBBCCBBBBBBCBBBCBCBBCBBBBBBCBBBCBCBBBBBCBCBBBCBBBBBCCCBBBBBCBBBBBCBBBBBCBCBBBCBBBBBBBBBBBCBBBBBB...
result:
ok good plan!
Subtask #10:
score: 7
Accepted
Test #10:
score: 7
Accepted
time: 5ms
memory: 9776kb
input:
13
output:
BBCCBBCBCBBCBBCCBBCBBCBBBBBBBBCBCBBCBBCBBCCBCBBCBBCBBBBBCBBCBBCCBBBBBCBBBBBBBBBBBCBBCBCCBBBBBCBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBCBCBCCBBCBBCCBCBCCBBCBBBBBCBBCBBCBBCCBCBBCCBBCBCCBCCBCBCCBBCCBCBBCBBCBBBBBCCBCBBCBBCBBBBBBBBBBBBCBCCBCBCCBBCCBCBBCBBCBBBCBCBBCBBCBBBBBBCBBBBBBBBBBBCBBCBCCBBBBBCBBBBBBBBBBBBBB...
result:
ok good plan!
Subtask #11:
score: 6
Accepted
Test #11:
score: 6
Accepted
time: 6ms
memory: 13304kb
input:
14
output:
BCBBBCBCBBBBBBBBBCBBBBBCBBBBBCBCBBBBBBBBBBBCBBBBBBBBBBBBBBBBBBBBBCBBBBBCBBBBBCBBBBBCBCBBBCBBBBBCBBBBBCBBBBBBBBBBBCBBBBBCBBBBBCBBBBBBBBBBBBBCBBBBBBBBBBBBBBBBBBBBBBBCBBBBBCBBBBBCBBBBBBBBBBBCBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBCCCBBBBBCBBBBBCBBBBBCBCBBBCBBBBBCBBBBBCBBBBBB...
result:
ok good plan!
Subtask #12:
score: 6
Accepted
Test #12:
score: 6
Accepted
time: 14ms
memory: 16976kb
input:
15
output:
BBCCBBCBCBBCBBCCBBCBBCBBBBBBBBCBCBBCBBCBBCCBCBBCBBCBBBBBCBBCBBCCBBCBBCBBBBBBBBBBBCBBCBCCBBBBBCBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBCBCBBCBBCBBCCBCBCCBBCBBBBBCBBCBBCBBCCBCBBCCBBCBCCBCBBCBCCBBCCBCBBCBBCBBBBBCBBCBBCBBBBBBBBBBBBBBBBBCCBCBCCBBCCBCBBCBBCBBBBBCBBCBBCBBBBBBCBBBBBBBBBBBCBBCBCCBBBBBCBBBBBBBBBBBBBB...
result:
ok good plan!
Subtask #13:
score: 6
Accepted
Test #13:
score: 6
Accepted
time: 31ms
memory: 29148kb
input:
16
output:
BCBBBCBCBBBBBBBBBCBBBBBCBBBBBCBCBBBBBBBBBBBCBBBBBBBBBBBBBBBBBBBBBCBBBBBCBBBBBCBBBBBCBCBBBCBBBBBCBBBBBCBBBBBBBBBBBCBBBBBCBBBBBCBCBBBBBBBBBBBCBBBBBBBBBBBBBBBBBBBBBBBCBBBBBCBBBBBCBBBBBBBBBBBCBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBCBBBBBCBBBBBCBBBBBCBCBBBCBBBBBCBBBBBCBBBBBB...
result:
ok good plan!
Subtask #14:
score: 6
Accepted
Test #14:
score: 6
Accepted
time: 56ms
memory: 47012kb
input:
17
output:
BBCCBBCBCBBCBBCCBBCBBCBBBBBBBBCBCBBCBBCBBCCBCBBCBBCBBBBBCBBCBBCCBBCBBCBBBBBBBBBBBCBBCBCCBBBBBCBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBCBCBBCBBCBBCCBCBCCBBCBBBBBCBBCBBCBBCCBCBBCCBBCBCCBCBBCBCCBBCCBCBBCBBCBBBBBCBBCBBCBBBBBBBBBBBBBBBBBCBBCBCCBBCCBCBBCBBCBBBBBCBBCBBCCBBBBBCBBBBBBBBBBBCBBCBCCBBBBBCBBBBBBBBBBBBBB...
result:
ok good plan!
Subtask #15:
score: 0
Wrong Answer
Test #15:
score: 0
Wrong Answer
time: 1100ms
memory: 174936kb
input:
18
output:
BCCBBBCBBBBBCCBCCBBBBBBBBCBCCBCCBBBBBBBBBBBBBBCBBCBBBBBBBBBBCCCCBBBBBBBBBBBBBBBBBBBBBBBBBBBBCBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB...
result:
wrong answer the length of the string should be 131072