QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#526776#4327. ŠeširiDecember456100 ✓159ms96752kbC++141.9kb2024-08-21 20:13:552024-08-21 20:13:57

Judging History

你现在查看的是最新测评结果

  • [2024-08-21 20:13:57]
  • 评测
  • 测评结果:100
  • 用时:159ms
  • 内存:96752kb
  • [2024-08-21 20:13:55]
  • 提交

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;
}

详细

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