QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#526681#4327. ŠeširiDecember4560 1069ms173156kbC++142.0kb2024-08-21 19:21:092024-08-21 19:21:11

Judging History

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

  • [2024-08-21 19:21:11]
  • 评测
  • 测评结果:0
  • 用时:1069ms
  • 内存:173156kb
  • [2024-08-21 19:21:09]
  • 提交

answer

#include <cstdio>

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) {
// printf("%d %d\n", u, 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 st = 0; st < 1 << (n + 1); st ++) {
        cur[st] = h[st];
    }
    for (int st = 0; st < 1 << (n + 1); st ++) {
        if (cur[st]) {
            solve(cur[st]);
        }
    }

// printf("Euler:");
// for (int i = 0; i < len; i ++) {
//     printf(" %d", euler[i]);
// }
// putchar('\n');
// printf("edge count: %d\n", eCnt >> 1);
    for (int i = 0; i < n; i ++) {
        id[1 << i] = i;
    }
    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;
// printf("res: %d, v: %d\n", (euler[i] & all) >> (u + 1) << u | (euler[i] & tmp), euler[i]);
        ans[u][(euler[i] & all) >> (u + 1) << u | (euler[i] & tmp)] = 'B' ^ (bool){euler[i] >> n};
    }

    for (int i = 0; i < n; i ++) {
        printf("%s\n", ans[i]);
    }

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 9720kb

input:

4

output:

CCBCCCBC




result:

wrong output format Unexpected end of file - token expected

Subtask #2:

score: 0
Wrong Answer

Test #2:

score: 0
Wrong Answer
time: 1ms
memory: 7708kb

input:

5

output:

CCBCCCCBBCBCCCBC
CBCBBCCCCCBBCBCC
BCBCBBBCCBCBBCBB
CBCBCCCBBCBCCCBB
BCBBBBBCCBBBBBCB

result:

wrong answer your plan fails on CBBBB

Subtask #3:

score: 0
Wrong Answer

Test #3:

score: 0
Wrong Answer
time: 1ms
memory: 7688kb

input:

6

output:

CBCCCCCBBCCCBCBCCCCCBBCCCCCCCBBC






result:

wrong output format Unexpected end of file - token expected

Subtask #4:

score: 0
Wrong Answer

Test #4:

score: 0
Wrong Answer
time: 1ms
memory: 7716kb

input:

7

output:

CCCCCCCB
C
C
B
B
C
B

result:

wrong answer the length of the string should be 64

Subtask #5:

score: 0
Wrong Answer

Test #5:

score: 0
Wrong Answer
time: 0ms
memory: 7752kb

input:

8

output:

CBCCBCCBCCCCCBCCCCCCCBCCCCBCCCCBBCCBCCBCCBBCBCCCCCBCCCCCBCCBCCBCCCCCBCCCBCCCCCCCCCCCCCCCCCBCBCCCBCCCCCBCCBBCBCCCCBBCBCCCBCCBCBBC








result:

wrong output format Unexpected end of file - token expected

Subtask #6:

score: 0
Wrong Answer

Test #6:

score: 0
Wrong Answer
time: 0ms
memory: 9828kb

input:

9

output:

CCCCBCCCCCCBCCBCCCCBCCBCCCBCCCCBBCCCCCBCBCBCCCCCCCBCCCCBCCCCCCCCCCCBBCBCCCBCCCCCCCBCBCCBCCCCCBCCCCBCCCCBBCCCCCBCCCCCCBCCCCBBBBB









result:

wrong answer the length of the string should be 256

Subtask #7:

score: 0
Wrong Answer

Test #7:

score: 0
Wrong Answer
time: 0ms
memory: 9856kb

input:

10

output:

CBCCBCCBCCCCCCBCBCCBCCBCCCBCBCCBCCCCCCBCCCBCCCCCCCBCBCCBCCCCCBCCBCCBCCBCCCBCBCCCCCBCCCCBBCCCCBCCCCBCCCCBBCCCCCBCBCCCCBCCCCBCBCCBCCCCCCBCCCBCCCCBCCBCCCCCBCCBCCBCCCBCCCCBBCCCCCBCCCCBCCBCCCBCCCCCCCBCCCCBBCCCCCBCCCCBCCBCCCBCCCCBBCCCCBCCCCBCBCCCCCBCCCCCBCCBCCBCCCCCCCCCCCCCCCCCBCCCCCCCCCCCCCCCBCCCCCCCCCCC...

result:

wrong output format Unexpected end of file - token expected

Subtask #8:

score: 0
Wrong Answer

Test #8:

score: 0
Wrong Answer
time: 0ms
memory: 12156kb

input:

11

output:

CCCCBCCBCCCCCCBCBCCCCCBCCCBCCCCCCCCBCCBCCCBCBCCBCCBCBCCCCCCBCCBCBCCCCCCCCCBCCCCCCCBCBCCBCCCCCBCCCCBCBCCCCCCBCCBCCCCCCBCCCCBCCCCBCCCBCCBCCCBCBCCBCCBCBCCCCCBBCCBCCCBCBCCCCCCBCCBCBCCBCCBCCCBCBCCCCCBCBCCCCCCBCCBCCCCCCBCCCCBCCCCBBCCBCCBCCCBCBCCCCCBCCCCBBCCCCCBCCCCCCBCCCCBCCCCCBCBCBCCBCCBCCBCCBCBCBCCCCCCB...

result:

wrong answer the length of the string should be 1024

Subtask #9:

score: 0
Wrong Answer

Test #9:

score: 0
Wrong Answer
time: 2ms
memory: 6608kb

input:

12

output:

CCBCCCCBBCCCCCBCCCCCCCBCBCBCCCCCBCCBCCBCCCBCBBBBCCBCCCCBBCCCCCBCCCCBCCBCCCBCBCCBCCBCCBBCBCCBCCBCCCBCCCCBBCCCCBCCBCCCCBCCCCBCBCCCBCCCCCBCCCBCCCCCCCBCCCCBBCCCCCBCBBBCBCCBBCCCCCBCCCCBCCBCCCBCCCCBCCBCCCCBBCCCCCBCCCCCCBCCCCBCBCCBBCCBCCBCCCBCCCCCCCBCCCCCBCCBCCBCCCCBCCBCCCBCBCCBBCBCCCCCBCCBCCBCCCBCCCCBBCCC...

result:

wrong output format Unexpected end of file - token expected

Subtask #10:

score: 0
Wrong Answer

Test #10:

score: 0
Wrong Answer
time: 3ms
memory: 8452kb

input:

13

output:

CBCCBCCCCCCBCCBCBCCBCCBCCCBCCCCBCCCCCCBCCCBCBCCCCCBCCCCBCCCCCBCCBCCBCCBCCCBCCCCCCCBCBCCBCCCCCBCCCCBCCCCBCCCCCCBCCCCCCBCCCCCCCCCBCCCCCCBCCCBCBCCBCCBCCCCCBCCBCCBCCCBCCCCBBCCCCCBCCCCBCCBCCCBCCCCCCCBCCCCBCCCCCCBCCCCBCCBCCCBCCCCBBCCCCBCCCCBCCCCCCCCCCCCBBCCCCCBCCCCBCCBCCCBCCCCCCCBCBCCBCCCCCBCCCCBCCCCBBCCC...

result:

wrong answer the length of the string should be 4096

Subtask #11:

score: 0
Wrong Answer

Test #11:

score: 0
Wrong Answer
time: 7ms
memory: 16528kb

input:

14

output:

CCCCCCCBCCCCCBCCCCCCCBCCCBCCBCCBCCCBCCBCCBCCBCCCCBCCBBBCCCCBCCBC














result:

wrong answer the length of the string should be 8192

Subtask #12:

score: 0
Wrong Answer

Test #12:

score: 0
Wrong Answer
time: 13ms
memory: 18192kb

input:

15

output:

CCCCCCCBCCCCCCCC
C
C
C
C
C
C
B
B
B
B
B
B
B
B

result:

wrong answer the length of the string should be 16384

Subtask #13:

score: 0
Wrong Answer

Test #13:

score: 0
Wrong Answer
time: 28ms
memory: 33476kb

input:

16

output:

BBCCCCCBCCCCCCBCCCCBCCBCCCBCBCCCBCCCCCBCCCBCCCCBCCBCCCCCBCCBCCBCCCCBCCBCCCBCBCCBCCBCCCCCBBCBCCBCCCBCCCCCBCCBCCBCBCCCCBCCCCBCCCCBBCCCCCBCCCBCCCCCCCBCCCCCBCCBCCBCCCBCCCCCBCCBCCBCCCCBCCBCCCBCBCCCCCBCCCCCBCCBCCBCBCCCCBCCCCBCCCCBCCCBCCBCCCBCBCCCCCBCCCCBBCCCCCBCCCCBCCBCCCBBCCCBCCBCBCCCCCCBCCBCCCBCCCBCBCCB...

result:

wrong answer the length of the string should be 32768

Subtask #14:

score: 0
Wrong Answer

Test #14:

score: 0
Wrong Answer
time: 66ms
memory: 48532kb

input:

17

output:

CBCCBCCBCCCCCCCCBCCBCCBCCCBCBCCBCCCCCCBCCCBCCCCCCCBCCCCCBCCBCCBCBCCBCCBCCCBCCCCCBCBCBCCBCCCCCCBCCCBCCCCCBCCBCCBCCCCBCCBCCCBCBCCBCCCCCCBCCCBCBCCBCCBCCCCCBCCBCCBCCCBCCCCCBCCBCCBCBCCCCCBCCCBCCCCCCCBCCCCCBCCBCCBCBCCCCCBCCCBCCCCCCCCBCCBCCCBCBCCBCCBCBCCBCCCCCCBCCCCBCCBCCCBCCCCCCCBCBCCBCCCCCBCCCCBCCCCCBCCB...

result:

wrong answer the length of the string should be 65536

Subtask #15:

score: 0
Wrong Answer

Test #15:

score: 0
Wrong Answer
time: 1069ms
memory: 173156kb

input:

18

output:

CCCBBBCBCBBBCCBBCBBBBBBBBCBBCBCCBBBBBBBBBBBBBBCBBBBBBBBBBBBBCCCCBBBBBBBBBBBBBBBBBBBBBBBBBBBBCBCCBBBBBBCBBBBBBBBBBBBBBBCBBBBBBBCCBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBCCBBBBBBCCBBBBBBBBBBBBBBBBBBBBBBCCBBBBBBBBBBCBBBBCBBBBBBBBBBBCBBCCBBBBBBBBBBBBBBBBBBBBCBBCBBBBBBCCBBBBBBBBBBBBBBBBCBBCBBBCBBBBBBBBBBBBBBBBBBBB...

result:

wrong answer the length of the string should be 131072