QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#526776 | #4327. Šeširi | December456 | 100 ✓ | 159ms | 96752kb | C++14 | 1.9kb | 2024-08-21 20:13:55 | 2024-08-21 20:13:57 |
Judging History
answer
#include <cstdio>
#include <algorithm>
constexpr int MAXN = 19;
constexpr int MAXV = 1 << MAXN;
constexpr int MAXM = (MAXN + 1) * MAXV;
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;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 7
Accepted
Test #1:
score: 7
Accepted
time: 0ms
memory: 12904kb
input:
4
output:
BCBBBCBB BBCCCBCB CCBBCCCC CBCCBBBC
result:
ok good plan!
Subtask #2:
score: 7
Accepted
Test #2:
score: 7
Accepted
time: 2ms
memory: 12328kb
input:
5
output:
BBCCBBBBCBBCBBCB BCBBCCCCBCCBCCBB CBCCBBBBCCBCCCBC CCBBCCCCBBCBBBCC CBCCBCCBCCBCCCBC
result:
ok good plan!
Subtask #3:
score: 7
Accepted
Test #3:
score: 7
Accepted
time: 0ms
memory: 12812kb
input:
6
output:
BCBBBCBBBBBBBBBCCCBBBBCBBBCBBCBB BBCCBBCBCCBCBBCBBBBBBCBCCBBCCBBB BCBBCCBCBBCBCCBCCCCCCBCBBCCCBBCB CBCCBBCBCCBCBCBCCBCBBCCBCBBBCCCC CCBBCCCCBBBBCBCBCCBCBBBCCCCCBBCC CBCCBCCBCCCCCCBCBBCCCCCCBCCBCBBC
result:
ok good plan!
Subtask #4:
score: 7
Accepted
Test #4:
score: 7
Accepted
time: 3ms
memory: 13364kb
input:
7
output:
BBCCBBCBCBBCBBCBBBBBBCBBBBBBBBBBCBCCBBCBBCCBCBBCBBCBBCBBCCBCCBCB BCBBCCBCBBCBCCBCCCCCBBCBBCCBCCBCBBBBBCBBBBBCBCBBCCBBCBCCBBCBBCBB BBCCBBCBCCBCBBCBBBBBCCBCCBBCBBBBCBCCBBCBCCCCCCBCBBCCBCBCCBBBCCBB CCBBCCBCBBCBCCBCCCBCBBCBBCBCCBCCBCCBCCBCBBCBBBCBCCBBCBCBBCCCBBCC CBCCBBCBCCBCCCBCBBCBBCBBCCBBBCCBCCBCBCBB...
result:
ok good plan!
Subtask #5:
score: 7
Accepted
Test #5:
score: 7
Accepted
time: 4ms
memory: 13848kb
input:
8
output:
BCBBBCBCBBBBBBBBBCBBBBBCBBBCBBBBCBBBBBBCBBBBBCBBBBBCCCBBCCBBBBBCCCBBBBCBBBBCCBBBBBBBCBBBCBBBBBBBBBCBCCBBCBBBBBCBCCBBBBCCCBCBBCBB BBCCBBCBCCBCBBCCBBCBBCBBBBBBBCCCCCBCBBCBBCCCCBBBBBCBBBBBCBCCBBCBBBBBBCBCCBCBBCBBBBCCBCBBBCBBBBCCCCBCBBBBBCBBCBBCBBBBCCBBBCBCCBBB BCBBCCBCBBCBCCBCCCBCBBCBBCCBCCBBBBCBBCBCBB...
result:
ok good plan!
Subtask #6:
score: 7
Accepted
Test #6:
score: 7
Accepted
time: 0ms
memory: 15644kb
input:
9
output:
BBCCBBCBCBBCBBCCBBBBBCBBBBBBBBCBCBCCBBCBBCCBCBBCBBCBBBBBCBBCBBCBBBBBBCBBBBBBBBBBBCBBCBCCBBBBBCBBBBBBBBBBBBBBBBBBBCBBBBBBBBBBBBBBCBCCBBCBBCCBCBCCBBCBBBBBCBBCBBCBBCCBCBBCCBBCBCCBCCBCBCCBBCCBCBBCBBCBBBCBCCCCBBCBBCBBBBBBBBBBBBBBCCBCBCCBBCCBCCBCCBCBBCBBCCBCCBCB BCBBCCBCBBCBCCBBCCCCBBCCBCCBCCBCBBBBCCBBBBB...
result:
ok good plan!
Subtask #7:
score: 7
Accepted
Test #7:
score: 7
Accepted
time: 2ms
memory: 15376kb
input:
10
output:
BCBBBCBCBBBBBBBBBCBBBBBCBBBBBCBBBBBBBBBBBBBCBBBBBBBBBBBBBBBBBBBCCCBBBBBCBBBBBCBBBBBCBCBBBCBBBBBBBBBBBCBBCBBBBBBBCCBBBBBCBBBBBCBBCBBBBBBBBBBCBBBBBBBBBBBBCBBBBBBBBBBCCBBBCCBBBBBCCBBBBBBBBBBCBBBBBBBBCBBBCBBBBBBBCBBBBBBBBBBBCBBBCBBBBBBBBBBBCBBBBBCBBBBBCBBBBBBCCCBBBBCCBBBBCCBBBBBCCCBBCCBBBBBCBBBBCCBBCBBB...
result:
ok good plan!
Subtask #8:
score: 7
Accepted
Test #8:
score: 7
Accepted
time: 0ms
memory: 15960kb
input:
11
output:
BBCCBBCBCBBCBBCCBBCBBCBBBBBBBBCBCBBCBBCBBCCBCBBCBBCBBBBBCBBCBBCBBBBBBCBBBBBBBBBBBCBBCBCCBCBBBCBBBBBBBBBBBCBBBBBBBBBBBBBBBBBBBBBBCBCCBBCBBCCBCBCCBBCBBCBBCCBCBBCBBCCBCBBCCCBCBCCBCBBCBCCBBCCBCBCCBBCBBCBBCCCCBBCBBBBBBBBBBBBBBBBBCBBCBCCBBCCBCBCCBBCBBBCBCBBCBBCBBBBBBCBBBBBBBBBBBCBBCCCCBBBBBCBBBBBBBBBBBBBB...
result:
ok good plan!
Subtask #9:
score: 7
Accepted
Test #9:
score: 7
Accepted
time: 0ms
memory: 18492kb
input:
12
output:
BCBBBCBCBBBBBBBBBCBBBBBCBBBBBCBCBBBBBBBBBBBCBBBBBBBBBBBBBBBBBBBCBCBBBBBCBBBBBCBBBBBCBCBBBCBBBBBBBBBBBCBBBBBBBBBBBCBBBBBCBBBBBCBBCBBBBBBBBBBCBBBBBBBBBBBBBBBBBBBCBBBCBBBBBCBBBBBBBBBBBBBBBBBCBBBBBBBBBBBBBBBBBBBCCBBBBBBCBBBCBCBBCBBBBBBCBBBCBCBBBBBCBCBBBCBBBBBCCCBBBBBCBBBBBCBBBBBCBCBBBCBBBBBBBBBBBCBBBBBB...
result:
ok good plan!
Subtask #10:
score: 7
Accepted
Test #10:
score: 7
Accepted
time: 0ms
memory: 20616kb
input:
13
output:
BBCCBBCBCBBCBBCCBBCBBCBBBBBBBBCBCBBCBBCBBCCBCBBCBBCBBBBBCBBCBBCCBBBBBCBBBBBBBBBBBCBBCBCCBBBBBCBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBCBCBCCBBCBBCCBCBCCBBCBBBBBCBBCBBCBBCCBCBBCCBBCBCCBCCBCBCCBBCCBCBBCBBCBBBBBCCBCBBCBBCBBBBBBBBBBBBCBCCBCBCCBBCCBCBBCBBCBBBCBCBBCBBCBBBBBBCBBBBBBBBBBBCBBCBCCBBBBBCBBBBBBBBBBBBBB...
result:
ok good plan!
Subtask #11:
score: 6
Accepted
Test #11:
score: 6
Accepted
time: 7ms
memory: 21120kb
input:
14
output:
BCBBBCBCBBBBBBBBBCBBBBBCBBBBBCBCBBBBBBBBBBBCBBBBBBBBBBBBBBBBBBBBBCBBBBBCBBBBBCBBBBBCBCBBBCBBBBBCBBBBBCBBBBBBBBBBBCBBBBBCBBBBBCBBBBBBBBBBBBBCBBBBBBBBBBBBBBBBBBBBBBBCBBBBBCBBBBBCBBBBBBBBBBBCBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBCCCBBBBBCBBBBBCBBBBBCBCBBBCBBBBBCBBBBBCBBBBBB...
result:
ok good plan!
Subtask #12:
score: 6
Accepted
Test #12:
score: 6
Accepted
time: 16ms
memory: 26020kb
input:
15
output:
BBCCBBCBCBBCBBCCBBCBBCBBBBBBBBCBCBBCBBCBBCCBCBBCBBCBBBBBCBBCBBCCBBCBBCBBBBBBBBBBBCBBCBCCBBBBBCBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBCBCBBCBBCBBCCBCBCCBBCBBBBBCBBCBBCBBCCBCBBCCBBCBCCBCBBCBCCBBCCBCBBCBBCBBBBBCBBCBBCBBBBBBBBBBBBBBBBBCCBCBCCBBCCBCBBCBBCBBBBBCBBCBBCBBBBBBCBBBBBBBBBBBCBBCBCCBBBBBCBBBBBBBBBBBBBB...
result:
ok good plan!
Subtask #13:
score: 6
Accepted
Test #13:
score: 6
Accepted
time: 29ms
memory: 36668kb
input:
16
output:
BCBBBCBCBBBBBBBBBCBBBBBCBBBBBCBCBBBBBBBBBBBCBBBBBBBBBBBBBBBBBBBBBCBBBBBCBBBBBCBBBBBCBCBBBCBBBBBCBBBBBCBBBBBBBBBBBCBBBBBCBBBBBCBCBBBBBBBBBBBCBBBBBBBBBBBBBBBBBBBBBBBCBBBBBCBBBBBCBBBBBBBBBBBCBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBCBBBBBCBBBBBCBBBBBCBCBBBCBBBBBCBBBBBCBBBBBB...
result:
ok good plan!
Subtask #14:
score: 6
Accepted
Test #14:
score: 6
Accepted
time: 74ms
memory: 51040kb
input:
17
output:
BBCCBBCBCBBCBBCCBBCBBCBBBBBBBBCBCBBCBBCBBCCBCBBCBBCBBBBBCBBCBBCCBBCBBCBBBBBBBBBBBCBBCBCCBBBBBCBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBCBCBBCBBCBBCCBCBCCBBCBBBBBCBBCBBCBBCCBCBBCCBBCBCCBCBBCBCCBBCCBCBBCBBCBBBBBCBBCBBCBBBBBBBBBBBBBBBBBCBBCBCCBBCCBCBBCBBCBBBBBCBBCBBCCBBBBBCBBBBBBBBBBBCBBCBCCBBBBBCBBBBBBBBBBBBBB...
result:
ok good plan!
Subtask #15:
score: 6
Accepted
Test #15:
score: 6
Accepted
time: 159ms
memory: 96752kb
input:
18
output:
BCBBBCBCBBBBBBBBBCBBBBBCBBBBBCBCBBBBBBBBBBBCBBBBBBBBBBBBBBBBBBBBBCBBBBBCBBBBBCBBBBBCBCBBBCBBBBBCBBBBBCBBBBBBBBBBBCBBBBBCBBBBBCBCBBBBBBBBBBBCBBBBBBBBBBBBBBBBBBBBBBBCBBBBBCBBBBBCBBBBBBBBBBBCBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBCBBBBBCBBBBBCBBBBBCBCBBBCBBBBBCBBBBBCBBBBBB...
result:
ok good plan!
Extra Test:
score: 0
Extra Test Passed