#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
const int Z = 10000;
mt19937 rng(time(nullptr));
int n, k, t, s;
string ss;
signed main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> k >> t >> ss;
if (k%2 == 0) {
cout << "-1\n";
return 0;
}
s = 0;
while (ss.size() < n) ss = "0"+ss;
for (int i = 0; i < n; i++) {
s += (1 << (n-i-1)) * (ss[i] == '1');
}
if (n <= 4) {
for (int zz = 0; zz < Z; zz++) {
vector<int> ans(1 << n);
for (int i = 0; i < (1 << n); i++) {
ans[i] = i;
if (i == s) swap(ans[0], ans[i]);
}
bool ok = 0;
shuffle(ans.begin()+1, ans.end(), rng);
for (int z = 0; z < Z; z++) {
int x = -1;
for (int i = 0; i+1 < (1 << n); i++) {
if (__builtin_popcount(ans[i] ^ ans[i+1]) != k) {
x = i;
break;
}
}
if (x == -1) {
ok = 1;
break;
}
int y = -1;
for (int i = x+2; i+1 < (1 << n); i++) {
if (__builtin_popcount(ans[i] ^ ans[i+1]) != k &&
__builtin_popcount(ans[x] ^ ans[i]) == k &&
__builtin_popcount(ans[x+1] ^ ans[i+1]) == k) {
y = i;
break;
}
}
if (y == -1) break;
reverse(ans.begin()+x+1, ans.begin()+y+1);
}
if (!ok) continue;
else {
cout << (1 << n) << "\n";
for (int i = 0; i < (1 << n); i++) {
for (int j = 0; j < n; j++) {
if ((ans[i] >> (n-j-1)) & 1) ss[j] = '1';
else ss[j] = '0';
}
cout << ss << "\n";
}
}
return 0;
}
cout << "-1\n";
}
else {
vector<int> ans((1 << n), -1);
vector<bool> vis((1 << n), 0);
ans[0] = 0;
vis[0] = 1;
for (int i = 1; i < (1 << n); i++) {
int x = ans[i-1];
for (int j = 0; j < n; j++) {
if (vis[x ^ (1 << j)]) continue;
ans[i] = x ^ (1 << j);
vis[x ^ (1 << j)] = 1;
break;
}
}
cout << (1 << n) << "\n";
for (int i = 0; i < (1 << n); i++) {
for (int j = 0; j < n; j++) {
if ((ans[i] >> (n-j-1)) & 1) ss[j] = '1';
else ss[j] = '0';
}
cout << ss << "\n";
}
}
}
Compilation message
lyuboyn.cpp: In function 'int main()':
lyuboyn.cpp:23:20: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
23 | while (ss.size() < n) ss = "0"+ss;
| ~~~~~~~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Ok |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Not a cycle! |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Ok |
| 2 |
Correct |
1 ms |
348 KB |
Ok |
| 3 |
Correct |
0 ms |
348 KB |
Ok |
| 4 |
Correct |
0 ms |
344 KB |
Ok |
| 5 |
Correct |
1 ms |
344 KB |
Ok |
| 6 |
Correct |
0 ms |
600 KB |
Ok |
| 7 |
Correct |
0 ms |
348 KB |
Ok |
| 8 |
Correct |
1 ms |
348 KB |
Ok |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
6492 KB |
Ok |
| 2 |
Correct |
9 ms |
3160 KB |
Ok |
| 3 |
Correct |
0 ms |
348 KB |
Ok |
| 4 |
Incorrect |
1 ms |
348 KB |
Not a cycle! |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Fail, not exactly k bits are different: line = 0 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
6320 KB |
First number in answer is not x 44202 0 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
6492 KB |
Ok |
| 2 |
Correct |
9 ms |
3160 KB |
Ok |
| 3 |
Correct |
0 ms |
348 KB |
Ok |
| 4 |
Incorrect |
1 ms |
348 KB |
Not a cycle! |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
3164 KB |
First number in answer is not x 92826 0 |
| 2 |
Halted |
0 ms |
0 KB |
- |
