QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#121107 | #4327. Šeširi | hos_lyric | 100 ✓ | 265ms | 21920kb | C++14 | 2.5kb | 2023-07-07 15:53:49 | 2023-07-07 15:53:51 |
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; }
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