#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math,inline")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,lzcnt,mmx,abm,avx,avx2,fma")
#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 || __builtin_popcount(ans[0] ^ ans.back()) != k) 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 if (k == 1) {
vector<int> ans((1 << n), -1);
vector<bool> vis((1 << n), 0);
ans[0] = 0;
vis[0] = 1;
bool ok = 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;
}
if (ans[i] == -1) ok = 0;
}
if (!ok) {
cout << "-1\n";
return 0;
}
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";
}
}
else if (k == 3) {
vector<int> ans((1 << n), -1);
vector<bool> vis((1 << n), 0);
ans[0] = 0;
vis[0] = 1;
bool ok = 1;
for (int i = 1; i < (1 << n); i++) {
int x = ans[i-1];
for (int j = 0; j < n && ans[i] == -1; j++) {
for (int j2 = j+1; j2 < n && ans[i] == -1; j2++) {
for (int j3 = j2+1; j3 < n; j3++) {
if (vis[x ^ (1 << j) ^ (1 << j2) ^ (1 << j3)]) continue;
ans[i] = x ^ (1 << j) ^ (1 << j2) ^ (1 << j3);
vis[x ^ (1 << j) ^ (1 << j2) ^ (1 << j3)] = 1;
break;
}
}
}
if (ans[i] == -1) ok = 0;
}
if (!ok) {
cout << "-1\n";
return 0;
}
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";
}
}
else {
vector<int> almacenDeVideosParaAdultosDeEsomer;
for (int i = 0; i < (1 << n); i++) {
if (i != s && __builtin_popcount(i) == k) {
almacenDeVideosParaAdultosDeEsomer.push_back(i);
}
}
shuffle(all(almacenDeVideosParaAdultosDeEsomer), rng);
int sz = almacenDeVideosParaAdultosDeEsomer.size();
vector<int> ans((1 << n), -1);
vector<bool> vis((1 << n), 0);
//cerr << s << endl;
ans[0] = s;
vis[s] = 1;
bool ok = 1;
for (int i = 1; i < (1 << n); i++) {
int x = ans[i-1];
while (1) {
int j2 = rng() % sz;
int y = almacenDeVideosParaAdultosDeEsomer[j2];
//cerr << x << " " << y << " " << (x ^ y) << endl;
if (vis[x ^ y]) continue;
ans[i] = x ^ y;
vis[x ^ y] = 1;
break;
}
if (ans[i] == -1) {
ok = 0;
break;
}
}
if (!ok) {
cout << "-1\n";
return 0;
}
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:25:20: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
25 | while (ss.size() < n) ss = "0"+ss;
| ~~~~~~~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Ok |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Ok |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Ok |
| 2 |
Correct |
0 ms |
348 KB |
Ok |
| 3 |
Correct |
0 ms |
348 KB |
Ok |
| 4 |
Correct |
0 ms |
424 KB |
Ok |
| 5 |
Correct |
0 ms |
348 KB |
Ok |
| 6 |
Correct |
0 ms |
348 KB |
Ok |
| 7 |
Correct |
0 ms |
348 KB |
Ok |
| 8 |
Correct |
0 ms |
344 KB |
Ok |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
27 ms |
6392 KB |
Ok |
| 2 |
Correct |
13 ms |
3164 KB |
Ok |
| 3 |
Correct |
1 ms |
344 KB |
Ok |
| 4 |
Correct |
0 ms |
348 KB |
Ok |
| 5 |
Correct |
0 ms |
348 KB |
Ok |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Ok |
| 2 |
Correct |
1 ms |
604 KB |
Ok |
| 3 |
Correct |
15 ms |
3120 KB |
Ok |
| 4 |
Correct |
8 ms |
1624 KB |
Ok |
| 5 |
Correct |
0 ms |
348 KB |
Ok |
| 6 |
Correct |
1 ms |
348 KB |
Ok |
| 7 |
Correct |
4 ms |
1116 KB |
Ok |
| 8 |
Correct |
0 ms |
348 KB |
Ok |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1026 ms |
1624 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
27 ms |
6392 KB |
Ok |
| 2 |
Correct |
13 ms |
3164 KB |
Ok |
| 3 |
Correct |
1 ms |
344 KB |
Ok |
| 4 |
Correct |
0 ms |
348 KB |
Ok |
| 5 |
Correct |
0 ms |
348 KB |
Ok |
| 6 |
Correct |
0 ms |
348 KB |
Ok |
| 7 |
Correct |
1 ms |
604 KB |
Ok |
| 8 |
Correct |
15 ms |
3120 KB |
Ok |
| 9 |
Correct |
8 ms |
1624 KB |
Ok |
| 10 |
Correct |
0 ms |
348 KB |
Ok |
| 11 |
Correct |
1 ms |
348 KB |
Ok |
| 12 |
Correct |
4 ms |
1116 KB |
Ok |
| 13 |
Correct |
0 ms |
348 KB |
Ok |
| 14 |
Execution timed out |
1026 ms |
1624 KB |
Time limit exceeded |
| 15 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1014 ms |
856 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
