QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#121107#4327. Šeširihos_lyric100 ✓265ms21920kbC++142.5kb2023-07-07 15:53:492023-07-07 15:53:51

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-07 15:53:51]
  • 评测
  • 测评结果:100
  • 用时:265ms
  • 内存:21920kb
  • [2023-07-07 15:53:49]
  • 提交

answer

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }


constexpr int MAX_N = 18;

int N;

// popcnt K <-> K+1
int K;
inline int side(int u) {
  return __builtin_popcount(u) - K;
}

int deg[1 << MAX_N];
bool dir[1 << MAX_N][MAX_N];

void dfs(int u) {
  const int s = side(u);
  assert(s == 0 || s == 1);
  for (int i = 0; i < N; ++i) if ((u >> i & 1) == s) {
    const int v = u ^ 1 << i;
    if (!dir[u][i] && !dir[v][i]) {
      --deg[u];
      --deg[v];
      dir[u][i] = true;
      dfs(v);
    }
  }
}

int main() {
  for (; ~scanf("%d", &N); ) {
    fill(deg, deg + (1 << N), 0);
    memset(dir, 0, sizeof(dir));
    for (K = 0; K < N; ++K) {
      for (int u = 0; u < 1 << N; ++u) {
        const int s = side(u);
        if (s == 0) deg[u] = N - K;
        if (s == 1) deg[u] = K + 1;
      }
      for (int u = 0; u < 1 << N; ++u) {
        for (; deg[u] & 1; ) {
          dfs(u);
        }
      }
      for (int u = 0; u < 1 << N; ++u) {
        for (; deg[u] > 0; ) {
          dfs(u);
        }
      }
    }
    
    for (int i = 0; i < N; ++i) {
      for (int p = 0; p < 1 << (N-1); ++p) {
        int u = 0;
        for (int j = 0; j < N - 1; ++j) {
          u |= (p >> ((N-1)-1-j) & 1) << ((j < i) ? j : (j + 1));
        }
        putchar(dir[u][i] ? 'B' : dir[u | 1 << i][i] ? 'C' : '?');
      }
      puts("");
    }
  }
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 7
Accepted

Test #1:

score: 7
Accepted
time: 3ms
memory: 8156kb

input:

4

output:

CCBBCCCC
BBCCBBCC
BBBBCCBC
BCCBBBCB

result:

ok good plan!

Subtask #2:

score: 7
Accepted

Test #2:

score: 7
Accepted
time: 0ms
memory: 8116kb

input:

5

output:

BBCBBBBBCCCCCBCC
BCBCCCCCBBBBBCBC
BBCCBBBBCCCCBBCC
BCBBCBBCBCBBBCBC
BBCCBBCBCCCCCBCB

result:

ok good plan!

Subtask #3:

score: 7
Accepted

Test #3:

score: 7
Accepted
time: 1ms
memory: 8780kb

input:

6

output:

CCBCCBBBBCBBBBBBCBCCCCCCCCBBCCCC
BBCBBCCCCBCCCCCCBCBBBBBBBBCCBBCC
BBBCCBBCBCBBBBBBCBCCCCCCCCBBCCCC
BBCBBCCBCBBBBBCCBCCCBBBBBBCCBBCC
BCBCCBCCBCBBBCBBCBBCBCCCBBBBCCBC
BBCCCBBCCCCCCCCBBBCCCCCBBCCBBBCB

result:

ok good plan!

Subtask #4:

score: 7
Accepted

Test #4:

score: 7
Accepted
time: 2ms
memory: 8180kb

input:

7

output:

BBCCBCCBCBBCBCBCBCCBBBBBBBBBBBBBCBBCCCCCCCCCCCCCCBCBBBBBCCCCCBCC
BCBBCBBCBCCBCBCBCBBCCCCCCCCCCCCCBCCBBBBBBBBBBBBBBCBCCCCCBBBBBCBC
BBCBBBBCCCCBCCBBBCCBBBBBBBBBBBBBCBBCCCCCCCCCCCCCBBCBBBBBCCCCCBCC
BCBCCCCBBBBCBBCCCBBCBCBCBCBCCCCCBCCBCBCBBBCBBBBBBCBCCCCCBBBBBCBC
BBCCBBBCCCCBCCBCBCCBBBCCBBCCBBBBCBBCBBCC...

result:

ok good plan!

Subtask #5:

score: 7
Accepted

Test #5:

score: 7
Accepted
time: 2ms
memory: 8312kb

input:

8

output:

CCBBCCCCBBCCCCBBCCBBBBCCBBBBCCCCBBCCCCBCBBCCBCCBBBBCBBBBBCBBBBBBCCBBBBCBCCBBCBBCCCCBCCCCCBCCCCCCCCBCCBBBBCBBBBBBCBCCCCCCCCBBCCCC
BBCCBBBBCCBBBBCCBBCCCCBBCCCCBBBBCCBBBBCBCCBBCBBCCCCBCCCCCBCCCCCCBBCCCCBCBBCCBCCBBBBCBBBBBCBBBBBBBBCBBCCCCBCCCCCCBCBBBBBBCBCCBBCC
BBBCCBBBBBBBBBCCCCCCCCBBCCCCBBBBBBCCCCBCBB...

result:

ok good plan!

Subtask #6:

score: 7
Accepted

Test #6:

score: 7
Accepted
time: 2ms
memory: 8292kb

input:

9

output:

BBCBBBBBCCCCCCBBBBBBCBCBCBBCBCCBCCCCBCBCBCCBCBBCBBCCCCCBBBBCBCBBBBBBCBBBCBBCBBBBBBBBBBBBBBBBBBBBBBBCBCCBBBBBBBBBBCCBBBBBBBBBBBBBCCCCBCCCBCCBCCCCCCCCCCCCCCCCCCCCCCCBCBBCCCCCCCCCCBBCCCCCCCCCCCCCCBCCBCCBCBBCBCBCBCCBBBBBBBBBBBBBCBBCCCCCCCCCCCCCCBCBBBBBCCCCCBCC
BCBCCCCCBBBBBBCCCCCCBCBCBCCBCBBCBBBBCBCBCBB...

result:

ok good plan!

Subtask #7:

score: 7
Accepted

Test #7:

score: 7
Accepted
time: 3ms
memory: 8168kb

input:

10

output:

CCBCCBBBBCBBBBCCCBCCCCBBCCCCBBBBBCBCBBCCCCCBCCCBCCBBCBBCBBCBBCCCCBCBCCBBBBBCBBBCBBCCBCCBCCBCCBBBBBBBCCCCBBCBCCCCCCBCBBBBBBBCCBBBBCBCBBCBCCCBCBBBCCBBCBBCBBBBBBBBBBCBBBBBCBBBBBBBBBBBBBBBBBBBBBBBBBBBBCCCBBCCCCBBBCBBBBCCBBBBCCCBBBCCCCBCBBCCBCCBBBBCBBBBBCBBBBBBCBCBCCBCBBBCBCCCBBCCBCCBCCCCCCCCCCBCCCCCBCCC...

result:

ok good plan!

Subtask #8:

score: 7
Accepted

Test #8:

score: 7
Accepted
time: 1ms
memory: 8304kb

input:

11

output:

BBCCBCCBCBBCBCBBBCCBBBCBBBBCBCCBCBBCCCBCCCCBCBBCCBCCCCCBBBBCBBCBBCCBBBCBBBBCBBBBCCBBBBBCCBBBBCCBCBBCBCCBBBBBBBBBBCCBBBBBBBBCBCBBCBBCCCBCCCCBCCCCBBCCCCCBBCCCCBBCBCCBCBBCCCCCCCCCCBBCCCCCCCCBCBCCBBCCCCCBBBBCBCBCCCCBBCCBBBBCBCBBBBBCCBBCCCCBCBCCCBCCCCBBBBCCBCBCBCCBBBBCBBBCBCBBCBBBBCBCBCBBBCCBCBBCBCCBBCCB...

result:

ok good plan!

Subtask #9:

score: 7
Accepted

Test #9:

score: 7
Accepted
time: 5ms
memory: 8656kb

input:

12

output:

CCBBCCCCBBCCCCBBCCBBBBCCBBBBCCCBBBCBCCBBBBBCBBBBBBCCBCCCCCBBCCCCCCBCBBCCCCCBCCCCCCBBCBBBBBCCBBBBCCCCBBBCCCBBBCCCBBCCCBBBCBBCCBBBBBCCCCCBBBCCCBBBBBCCCCCCCCBBCBBCCCCBCCCBCBCBCBBCCCBBBBBCBBBCBCCBCCBCCCCCBCCCCCBBCCCBCBCCCBBBCBBCBCCCCCCBBBCCCCCCCBBCBBCBCCBCBBBBCCBBBBBCCCBBBCCCCCBBBBBBBBCCBCCBBBBCBBBCBCBC...

result:

ok good plan!

Subtask #10:

score: 7
Accepted

Test #10:

score: 7
Accepted
time: 7ms
memory: 8648kb

input:

13

output:

BBCBBBBBCCCCCCBCBBBBCBCCCBBBBBBBCCCCBCBBBCCCCCCCBBCBCBBBBCCCCCBBBBBBCBCCCBBBBCCBBCBCBCCBCCCBCBBBBBBBBBBBBCCBCBBBBBBBCBBBCBBCCCBBCCCCBCBBBCCCCBBCCBCBCBBCBBBCBCCCCCCCCCCCCBBCBCCCCCCCBCCCBCCBBBCCCBCBCBBBBCCCCCBCCBBCCCCBCBBCCCBBBCCBBBBCBCCBBBCCBCBCCCBBBBCCBBCCBBBBCBCBCBBBBBCCBCBCBBCCCBCCCCCBBBBBBBBBBBBC...

result:

ok good plan!

Subtask #11:

score: 6
Accepted

Test #11:

score: 6
Accepted
time: 4ms
memory: 9028kb

input:

14

output:

CCBCCBBBBCBBBBCCCBCCCCBBCCCCBBBCBCBCBBCCCCCBCCCCCCBBCBBBBBCCBBBCCBCBCCBBBBBCBBBBBBCCBCCCCCBBCCCBBBBBCCCBBBCCCBBCCCBBBCCBBCCCBBBBBCBBBBBCCCBBBCCCCCBBBBBBBBCCBCCBBBBCBBBCBCBCBCCBBBCCCCCBCCCBCBBBBBCBBBBBCBBBBBCBBBBCBCBCBCCBBCCCCBBBBBBCCCBCBCCCBCCCCBBBBCBCBBBBCBCCCCCBBBCCCBBBBBCCCCCCCCBBCBBCCCCBCCCBCBCB...

result:

ok good plan!

Subtask #12:

score: 6
Accepted

Test #12:

score: 6
Accepted
time: 21ms
memory: 11020kb

input:

15

output:

BBCCBCCBCBBCBCBCBCCBBBCCBBBBBBBBCBBCCCBBCCCCCCCCCBCBCBBBBCCCCBCBBCCBBBCCBBBBBCCBCCBCBCCCCCCBCCCBCBBBBBBBBCCBCBBBBBBBCBBBCBBCBCBBCBBCCCBBCCCCCBBCBBCBCBBBBBBCBBBCBCCCCCCCCBBCBCCCCCCCBCCCBCCBCBCCBBCBCBBBBCCCCCBCCBBBCCCBCBBCBCBBBCCCBBBCBCCBCBCCBBCCCCBBBBCCBBCCBCCBBBCBBBBBBBCBCCBCBBCCCBCBCCCBCBBBBBBBBBBB...

result:

ok good plan!

Subtask #13:

score: 6
Accepted

Test #13:

score: 6
Accepted
time: 55ms
memory: 11568kb

input:

16

output:

CCBBCCCCBBCCCCBBCCBBBBCCBBBBCCCCBBCBCCBBBBBCBBBCBBCCBCCBCCBCCBBBCCBCBBCCCCCBCCCBCCBBCBBCBBCBBCCCCCCCBBBBCCBCBBBBBBCBCCCCCCCBBCCCBBCCCCCBBBCCCBBCBBCCCCCBCCBCCCCBCCCBCCCCCBCCCCCBCCBCBCCBBCCBCBBCCCBCCCCBBCCBCBCCCCCCCCBBCCCCBCCBBCCBCBBCBCBBBBBBCCCBCCBCBBCBCCCBCCBBBBBCCCBBBCCBCCBBBBBCBBCBBBBCBBBCBBBBBCBB...

result:

ok good plan!

Subtask #14:

score: 6
Accepted

Test #14:

score: 6
Accepted
time: 123ms
memory: 15584kb

input:

17

output:

BBCBBBBBCCCCCCBBBBBBCBCBCBBCBCCBCCCCBCBCBCCBCBBCBBCCCCCBBBBCBCBCBBBBCBCBCBBCBBBBBCBBBBBBCBBBBBBCBBBCBCCBBBBBBBBCBCCBBBBCBBBBCBCBCCCCBCBCBCCBCCCCCBCCCCCCBCCCCCCBCCCBCBBCCCCCCCCBCBBCCCCBCCCCBCBCCBCCCCCBBBBCBCBBCCCCBCCCBBBBCBCBBBBBCBBBCCCCBCBCCCBBCBCBBCBCCBCBBBBBCBCCCBBCBCBCBCBBBCBCCCBCBCCCBBBCBCCBBCCC...

result:

ok good plan!

Subtask #15:

score: 6
Accepted

Test #15:

score: 6
Accepted
time: 265ms
memory: 21920kb

input:

18

output:

CCBCCBBBBCBBBBCCCBCCCCBBCCCCBBBBBCBCBBCCCCCBCCCBCCBBCBBCBBCBBCCCCBCBCCBBBBBCBBBCBBCCBCCBCCBCCBBBBBBBCCCCBBCBCCCCCCBCBBBBBBBCCBBBBCBBBBBCCCBBBCCBCCBBBBBCBBCBBBBCBBBCBBBBBCBBBBBBBBCBCBBCCBBBBCCBBBCBBBBCCBBCBCBBBBBBBBCBBBBBCBBCCBBCBCCBCBCBCBCCBBBBBBCBCBBCBBBCCBCCCCCBBBCCCBBCBBCCCCCBCCBCCCCBCCCBCCCCCBCC...

result:

ok good plan!

Extra Test:

score: 0
Extra Test Passed