This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int N, K, T; string S;
cin >> N >> K >> T >> S;
// Adjacent elements in cycle is xored by some value v, where popcount(v) == K.
// For K = 1, the answer is encoded by "Gray Code". (Or, we could also create
// the sequence recursively.).
//
// Generate all bitmasks with popcount == K. Then, if those bitmasks form a
// Xor basis with size N, we can generate all 2^N possible bitmasks with those
// bitmasks in the basis. Note that, since the basis has size N, it is sufficient
// to solve the case for K = 1 on the basis - this would go through all 2^N
// possible combinations of basis exactly once, and adjacent only differn in 1
// ON/OFF basis.
//
// Time complexity: O(N 2^N).
vector<pair<int, int>> basis; // xor basis (reduced value, original value)
for (int mask = 0; mask < (1 << N); mask++) {
if (__builtin_popcount(mask) == K) {
pair<int, int> cur = {mask, mask};
for (auto i : basis) {
cur.first = min(cur.first, cur.first ^ i.first);
}
if (cur.first == 0) { // not independent
continue;
}
basis.emplace_back(cur);
for (int i = int(basis.size()) - 2; i >= 0; i--) { // basis is sorted in decreasing order
if (basis[i].first < basis[i + 1].first) {
swap(basis[i], basis[i + 1]);
}
}
}
}
if (basis.size() != N) { // cannot generate all 2^N masks
cout << -1 << '\n';
return 0;
}
vector<int> gray(1 << N); // gray code
for (int mask = 0; mask < (1 << N); mask++) {
gray[mask] = mask ^ (mask >> 1);
}
cout << (1 << N) << '\n';
for (int mask = 0; mask < (1 << N); mask++) {
int Xor = 0;
for (int i = 0; i < N; i++) {
if ((gray[mask] >> i) & 1) {
Xor ^= basis[i].second;
}
}
for (int i = 0; i < N; i++) {
cout << ((S[i] - '0') ^ ((Xor >> i) & 1));
}
cout << '\n';
}
return 0;
}
Compilation message (stderr)
lyuboyn.cpp: In function 'int main()':
lyuboyn.cpp:43:20: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
43 | if (basis.size() != N) { // cannot generate all 2^N masks
| ~~~~~~~~~~~~~^~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |