QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#120749#4327. Šeširihos_lyric#0 1ms5836kbC++143.0kb2023-07-07 10:38:242024-05-26 00:53:00

Judging History

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

  • [2024-05-26 00:53:00]
  • 评测
  • 测评结果:0
  • 用时:1ms
  • 内存:5836kb
  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-07 10:38:24]
  • 提交

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

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;
    }
    
    for (int u = 0; u < N; ++u) {
      for (int p = 0; p < 1 << (N-1); ++p) {
        const int pop = __builtin_popcount(p);
        // F[u][p] = ((pop & 1) != (u & 1)) ? 'C' : 'B';
        F[u][p] = "BC"[xrand() & 1];
      }
    }
    for (; ; ) {
      bool upd = false;
      for (int u = 0; u < N; ++u) {
        for (int p = 0; p < 1 << N; ++p) {
          if (!check(p) && "BC"[p >> u & 1] != f(u, p)) {
            upd = true;
            f(u, p) ^= 'B' ^ 'C';
          }
        }
      }
      if (!upd) break;
    }
    assert(check());
    
    for (int u = 0; u < N; ++u) {
      puts(F[u]);
    }
break;
  }
  return 0;
}

詳細信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

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

input:

4

output:

BBCCCBBB
CCCCBBCC
CBBBCCBB
BBCCBBBC

result:

wrong answer your plan fails on CCCC

Subtask #2:

score: 0
Time Limit Exceeded

Test #2:

score: 0
Time Limit Exceeded

input:

5

output:


result:


Subtask #3:

score: 0
Time Limit Exceeded

Test #3:

score: 0
Time Limit Exceeded

input:

6

output:


result:


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: