QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#120884#4327. Šeširihos_lyric#21 1ms3952kbC++143.8kb2023-07-07 12:14:132024-07-04 00:27:49

Judging History

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

  • [2024-07-04 00:27:49]
  • 评测
  • 测评结果:21
  • 用时:1ms
  • 内存:3952kb
  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-07 12:14:13]
  • 提交

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


unsigned xrand() {
  static unsigned x = 314159265, y = 358979323, z = 846264338, w = 327950288;
  unsigned t = x ^ x << 11; x = y; y = z; z = w; return w = w ^ w >> 19 ^ t ^ t >> 8;
}


constexpr int MAX_N = 18;

int N;
char F[MAX_N][(1 << (MAX_N - 1)) + 1];

char &f(int u, int p) {
  return F[u][(p & ((1<<u)-1)) | (p >> (u+1) << u)];
}
bool check(int p) {
  int all[2] = {};
  int cnt[2] = {};
  for (int u = 0; u < N; ++u) {
    ++all[p >> u & 1];
    if ("BC"[p >> u & 1] == f(u, p)) {
      ++cnt[p >> u & 1];
    }
  }
  for (int a = 0; a < 2; ++a) {
    if (all[a] / 2 > cnt[a]) {
for(int u=0;u<N;++u)cerr<<"BC"[p>>u&1];cerr<<" ";pv(cnt,cnt+2);
      return false;
    }
  }
  return true;
}

bool check() {
cerr<<"check ";pv(F,F+N);
  for (int p = 0; p < 1 << N; ++p) {
    if (!check(p)) {
      return false;
    }
  }
  return true;
}

bool dfs(int p) {
  if (p == 1 << N) {
    assert(check());
    return true;
  } else {
    int all[2] = {};
    all[1] = __builtin_popcount(p);
    all[0] = N - all[1];
    for (int q = 0; q < 1 << N; ++q) {
      int cnt[2] = {};
      cnt[0] = __builtin_popcount(q & ~p);
      cnt[1] = __builtin_popcount(q & p);
      if (all[0] / 2 == cnt[0] && all[1] / 2 == cnt[1]) {
        string str(N, '?');
        for (int u = 0; u < N; ++u) str[u] = "BC"[p >> u & 1];
        bool ok = true;
        for (int u = 0; u < N; ++u) if (q >> u & 1) {
          ok = ok && (f(u, p) == '?' || f(u, p) == str[u]);
        }
        if (ok) {
          for (int u = 0; u < N; ++u) if (q >> u & 1) swap(f(u, p), str[u]);
          if (dfs(p + 1)) return true;
          for (int u = 0; u < N; ++u) if (q >> u & 1) swap(f(u, p), str[u]);
        }
      }
    }
  }
  return false;
}

int main() {
  for (; ~scanf("%d", &N); ) {
if(N==3){
 strcpy(F[0],"BBCC");
 strcpy(F[1],"BCBC");
 strcpy(F[2],"BBCC");
 assert(check());
}
    for (int u = 0; u < N; ++u) {
      fill(F[u], F[u] + (1 << (N-1)), '?');
      F[u][1 << (N-1)] = 0;
    }
    
    dfs(0);
    
    for (int u = 0; u < N; ++u) {
      for (int pp = 0; pp < 1 << (N-1); ++pp) {
        int p = 0;
        for (int i = 0; i < N-1; ++i) p |= ((pp >> ((N-1)-1-i)) & 1) << i;
        putchar((F[u][p] == '?') ? 'B' : F[u][p]);
      }
      puts("");
    }
    
    cerr << string(1 << N, '-') << endl;
    for (int u = 0; u < N; ++u) {
      for (int p = 0; p < 1 << N; ++p) {
        cerr << (("BC"[p >> u & 1] == f(u, p)) ? f(u, p) : (char)tolower(f(u, p)));
      }
      cerr << endl;
    }
    cerr << string(1 << N, '-') << endl;
  }
  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: 3912kb

input:

4

output:

BBBBCBCC
BCCCBBBC
BCBBCCBB
BBBBCBCB

result:

ok good plan!

Subtask #2:

score: 7
Accepted

Test #2:

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

input:

5

output:

BBBBCBBBCBBBCCCC
BBCCCCCCBBBBBBCC
BCCCBBBCBCCCBBBB
BCBBBBBBCCBCCCBB
BBBBCBBBCBBBCCCB

result:

ok good plan!

Subtask #3:

score: 7
Accepted

Test #3:

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

input:

6

output:

BBBBBBBBCBBBCBBBCBBBCBBBCCCBCCCC
BBBBCBBCCBCCCCCCBBBBBBBBBBBBCBCC
BCCCCCCCBBBCBCCCBBBCBCCCBBBBBBBC
BCCCBBBCBCCCBBBBCCCCBCCCBCCCBBBB
BCBBBBBBCCBBBBBBCCBCCCBBCCCCCCBB
BBBBBBBBCBBBCBBBCBBBCBBBCCCBCCCB

result:

ok good plan!

Subtask #4:

score: 0
Time Limit Exceeded

Test #4:

score: 0
Time Limit Exceeded

input:

7

output:


result:


Subtask #5:

score: 0
Time Limit Exceeded

Test #5:

score: 0
Time Limit Exceeded

input:

8

output:


result:


Subtask #6:

score: 0
Time Limit Exceeded

Test #6:

score: 0
Time Limit Exceeded

input:

9

output:


result:


Subtask #7:

score: 0
Time Limit Exceeded

Test #7:

score: 0
Time Limit Exceeded

input:

10

output:


result:


Subtask #8:

score: 0
Time Limit Exceeded

Test #8:

score: 0
Time Limit Exceeded

input:

11

output:


result:


Subtask #9:

score: 0
Time Limit Exceeded

Test #9:

score: 0
Time Limit Exceeded

input:

12

output:


result:


Subtask #10:

score: 0
Time Limit Exceeded

Test #10:

score: 0
Time Limit Exceeded

input:

13

output:


result:


Subtask #11:

score: 0
Time Limit Exceeded

Test #11:

score: 0
Time Limit Exceeded

input:

14

output:


result:


Subtask #12:

score: 0
Time Limit Exceeded

Test #12:

score: 0
Time Limit Exceeded

input:

15

output:


result:


Subtask #13:

score: 0
Time Limit Exceeded

Test #13:

score: 0
Time Limit Exceeded

input:

16

output:


result:


Subtask #14:

score: 0
Time Limit Exceeded

Test #14:

score: 0
Time Limit Exceeded

input:

17

output:


result:


Subtask #15:

score: 0
Time Limit Exceeded

Test #15:

score: 0
Time Limit Exceeded

input:

18

output:


result: