QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#120749 | #4327. Šeširi | hos_lyric# | 0 | 1ms | 5836kb | C++14 | 3.0kb | 2023-07-07 10:38:24 | 2024-05-26 00:53:00 |
Judging History
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;
}
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: 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