QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#121004 | #4327. Šeširi | hos_lyric | 21 | 5ms | 3636kb | C++14 | 4.4kb | 2023-07-07 13:43:00 | 2023-07-07 13:43:02 |
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]) {
cerr<<p<<" ";
for(int u=0;u<N;++u)cerr<<"BC"[p>>u&1];
cerr<<" ";
for(int u=0;u<N;++u)cerr<<f(u,p);
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;
}
if (N == 4 || N == 8) {
for (int u = 0; u < N; u += 4) {
for (int p = 0; p < 1 << N; ++p) {
f(u + 0, p) = "BC"[p >> (u + 1) & 1];
f(u + 1, p) = "BC"[(p >> (u + 0) & 1) ^ 1];
f(u + 2, p) = "BC"[p >> (u + 3) & 1];
f(u + 3, p) = "BC"[(p >> (u + 2) & 1) ^ 1];
if ((p >> (u + 0) & 1) != (p >> (u + 1) & 1)) {
f(u + 2, p) = f(u + 3, p) = "BC"[p >> (u + 0) & 1];
}
}
}
assert(check());
} else {
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;
}
詳細信息
Subtask #1:
score: 7
Accepted
Test #1:
score: 7
Accepted
time: 0ms
memory: 3532kb
input:
4
output:
BBBBCCCC CCCCBBBB BCBBCCBC CBBBCCCB
result:
ok good plan!
Subtask #2:
score: 7
Accepted
Test #2:
score: 7
Accepted
time: 0ms
memory: 3532kb
input:
5
output:
BBBBCBBBCBBBCCCC BBCCCCCCBBBBBBCC BCCCBBBCBCCCBBBB BCBBBBBBCCBCCCBB BBBBCBBBCBBBCCCB
result:
ok good plan!
Subtask #3:
score: 7
Accepted
Test #3:
score: 7
Accepted
time: 5ms
memory: 3636kb
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
Dangerous Syscalls
Test #5:
score: 0
Dangerous Syscalls
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