#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define fs first
#define ss second
#define str string
#define all(a) a.begin(), a.end()
#define print(a) \
for (auto x : a) \
cout << x << ' '; \
cout << endl;
#define each(x, a) for (auto x : a)
vector<int> ans;
vector<bool> used;
int n, k, t, sx = 0;
bool good(int s1, int s2){
int ans = 0;
while(s1 > 0 or s2 > 0){
ans += (s1 % 2 != s2 % 2);
s1 /= 2;
s2 /= 2;
}
return ans == k;
}
bool dfs(int node, int step){
if(step == (1 << n) - 1){
if(t == 0){
ans.push_back(node);
return true;
}
if(good(sx, node))
ans.push_back(node);
else
return false;
return true;
}
used[node] = 1;
if(k == 1 or k == 17){
for (int i = 0; i < n; i++)
{
if (k == 1 and !used[node ^ (1 << i)] and dfs(node ^ (1 << i), step + 1))
{
ans.push_back(node);
return true;
}
else if (k == 17 and !used[node ^ (node ^ (1 << i))] and dfs(node ^ (node ^ (1 << i)), step + 1))
{
ans.push_back(node);
return true;
}
}
}
else if(k == 2 or k == 16){
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
if (k == 2 and !used[(node ^ (1 << i)) ^ (1 << j)] and dfs((node ^ (1 << i)) ^ (1 << j), step + 1))
{
ans.push_back(node);
return true;
}
else if (k == 16 and !used[node ^ ((node ^ (1 << i)) ^ (1 << j))] and dfs(node ^ ((node ^ (1 << i)) ^ (1 << j)), step + 1)){
ans.push_back(node);
return true;
}
}
}
}
else if(k == 3 or k == 15){
for(int i = 0; i < n; i ++){
for(int j = i + 1; j < n; j ++){
for(int x = j + 1; x < n; x ++){
if (k == 3 and !used[((node ^ (1 << i)) ^ (1 << j)) ^ (1 << x)] and dfs(((node ^ (1 << i)) ^ (1 << j)) ^ (1 << x), step + 1))
{
ans.push_back(node);
return true;
}
else if (k == 15 and !used[(node ^ ((node ^ (1 << i)) ^ (1 << j)) ^ (1 << x))] and dfs(node ^ (((node ^ (1 << i)) ^ (1 << j)) ^ (1 << x)), step + 1)){
ans.push_back(node);
return true;
}
}
}
}
}
else if (k == 4 or k == 14)
{
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
for (int x = j + 1; x < n; x++)
{
for(int i1 = x + 1; i1 < n; i1 ++){
if (k == 4 and !used[(((node ^ (1 << i)) ^ (1 << j)) ^ (1 << x)) ^ (1 << i1)] and dfs((((node ^ (1 << i)) ^ (1 << j)) ^ (1 << x)) ^ (1 << i1), step + 1))
{
ans.push_back(node);
return true;
}
else if (k == 14 and !used[node ^ ((((node ^ (1 << i)) ^ (1 << j)) ^ (1 << x)) ^ (1 << i1))] and dfs(node ^ ((((node ^ (1 << i)) ^ (1 << j)) ^ (1 << x)) ^ (1 << i1)), step + 1))
{
ans.push_back(node);
return true;
}
}
}
}
}
}
else if(k == 5 or k == 13){
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
for (int x = j + 1; x < n; x++)
{
for (int i1 = x + 1; i1 < n; i1++)
{
for(int i2 = i1 + 1; i2 < n; i2 ++){
if (k == 5 and !used[((((node ^ (1 << i)) ^ (1 << j)) ^ (1 << x)) ^ (1 << i1)) ^ (1 << i2)] and dfs(((((node ^ (1 << i)) ^ (1 << j)) ^ (1 << x)) ^ (1 << i1)) ^ (1 << i2), step + 1))
{
ans.push_back(node);
return true;
}
else if (k == 13 and !used[node ^ (((((node ^ (1 << i)) ^ (1 << j)) ^ (1 << x)) ^ (1 << i1)) ^ (1 << i2))] and dfs(node ^ (((((node ^ (1 << i)) ^ (1 << j)) ^ (1 << x)) ^ (1 << i1)) ^ (1 << i2)), step + 1))
{
ans.push_back(node);
return true;
}
}
}
}
}
}
}
else if (k == 6 or k == 12)
{
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
for (int x = j + 1; x < n; x++)
{
for (int i1 = x + 1; i1 < n; i1++)
{
for (int i2 = i1 + 1; i2 < n; i2++)
{
for(int i3 = i2 + 1; i3 < n; i3 ++){
if (k == 12 and !used[node ^ ((((((node ^ (1 << i)) ^ (1 << j)) ^ (1 << x)) ^ (1 << i1)) ^ (1 << i2)) ^ (1 << i3))] and dfs(node ^ ((((((node ^ (1 << i)) ^ (1 << j)) ^ (1 << x)) ^ (1 << i1)) ^ (1 << i2)) ^ (1 << i3)), step + 1))
{
ans.push_back(node);
return true;
}
else if (k == 6 and !used[((((((node ^ (1 << i)) ^ (1 << j)) ^ (1 << x)) ^ (1 << i1)) ^ (1 << i2)) ^ (1 << i3))] and dfs(((((((node ^ (1 << i)) ^ (1 << j)) ^ (1 << x)) ^ (1 << i1)) ^ (1 << i2)) ^ (1 << i3)), step + 1)){
ans.push_back(node);
return true;
}
}
}
}
}
}
}
}
else if(k == 7 or k == 11){
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
for (int x = j + 1; x < n; x++)
{
for (int i1 = x + 1; i1 < n; i1++)
{
for (int i2 = i1 + 1; i2 < n; i2++)
{
for (int i3 = i2 + 1; i3 < n; i3++)
{
for(int i4 = i3 + 1; i4 < n; i4 ++){
if (k == 7 and !used[((((((node ^ (1 << i)) ^ (1 << j)) ^ (1 << x)) ^ (1 << i1)) ^ (1 << i2)) ^ (1 << i3)) ^ (1 << i4)] and dfs(((((((node ^ (1 << i)) ^ (1 << j)) ^ (1 << x)) ^ (1 << i1)) ^ (1 << i2)) ^ (1 << i3)) ^ (1 << i4), step + 1))
{
ans.push_back(node);
return true;
}
else if (k == 11 and !used[node ^ (((((((node ^ (1 << i)) ^ (1 << j)) ^ (1 << x)) ^ (1 << i1)) ^ (1 << i2)) ^ (1 << i3)) ^ (1 << i4))] and dfs(node ^ (((((((node ^ (1 << i)) ^ (1 << j)) ^ (1 << x)) ^ (1 << i1)) ^ (1 << i2)) ^ (1 << i3)) ^ (1 << i4)), step + 1)){
ans.push_back(node);
return true;
}
}
}
}
}
}
}
}
}
else if (k == 8 or k == 10)
{
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
for (int x = j + 1; x < n; x++)
{
for (int i1 = x + 1; i1 < n; i1++)
{
for (int i2 = i1 + 1; i2 < n; i2++)
{
for (int i3 = i2 + 1; i3 < n; i3++)
{
for (int i4 = i3 + 1; i4 < n; i4++)
{
for(int i5 = i4 + 1; i5 < n; i5 ++){
if (k == 8 and !used[(((((((node ^ (1 << i)) ^ (1 << j)) ^ (1 << x)) ^ (1 << i1)) ^ (1 << i2)) ^ (1 << i3)) ^ (1 << i4)) ^ (1 << i5)] and dfs((((((((node ^ (1 << i)) ^ (1 << j)) ^ (1 << x)) ^ (1 << i1)) ^ (1 << i2)) ^ (1 << i3)) ^ (1 << i4)) ^ (1 << i5), step + 1))
{
ans.push_back(node);
return true;
}
else if (k == 10 and !used[node ^ ((((((((node ^ (1 << i)) ^ (1 << j)) ^ (1 << x)) ^ (1 << i1)) ^ (1 << i2)) ^ (1 << i3)) ^ (1 << i4)) ^ (1 << i5))] and dfs(node ^ ((((((((node ^ (1 << i)) ^ (1 << j)) ^ (1 << x)) ^ (1 << i1)) ^ (1 << i2)) ^ (1 << i3)) ^ (1 << i4)) ^ (1 << i5)), step + 1)){
ans.push_back(node);
return true;
}
}
}
}
}
}
}
}
}
}
else if(k == 9){
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
for (int x = j + 1; x < n; x++)
{
for (int i1 = x + 1; i1 < n; i1++)
{
for (int i2 = i1 + 1; i2 < n; i2++)
{
for (int i3 = i2 + 1; i3 < n; i3++)
{
for (int i4 = i3 + 1; i4 < n; i4++)
{
for (int i5 = i4 + 1; i5 < n; i5++)
{
for(int i6 = i5 + 1; i6 < n; i6 ++){
if (!used[((((((((node ^ (1 << i)) ^ (1 << j)) ^ (1 << x)) ^ (1 << i1)) ^ (1 << i2)) ^ (1 << i3)) ^ (1 << i4)) ^ (1 << i5)) ^ (1 << i6)] and dfs(((((((((node ^ (1 << i)) ^ (1 << j)) ^ (1 << x)) ^ (1 << i1)) ^ (1 << i2)) ^ (1 << i3)) ^ (1 << i4)) ^ (1 << i5)) ^ (1 << i6), step + 1))
{
ans.push_back(node);
return true;
}
}
}
}
}
}
}
}
}
}
}
used[node] = 0;
return false;
}
void solve(){
cin >> n >> k >> t;
str s;
cin >> s;
for(int i = s.size() - 1; i >= 0; i --){
if(s[i] == '1'){
sx += (1 << (s.size() - 1 - i));
}
}
if(k % 2 == 0){
cout << -1;
return;
}
used.resize((1 << n));
if(dfs(sx, 0)){
cout << (1 << n) << endl;
reverse(all(ans));
for(int i = 0; i < ans.size(); i ++){
str s = "";
for(int j = 0; j < n; j ++){
if(ans[i] % 2 == 0)
s += '0';
else
s += '1';
ans[i] >>= 1;
}
reverse(all(s));
cout << s << endl;
}
}
else{
cout << -1;
}
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
// cin >> t;
while (t--)
{
solve();
cout << endl;
}
}
Compilation message
lyuboyn.cpp: In function 'void solve()':
lyuboyn.cpp:290:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
290 | for(int i = 0; i < ans.size(); i ++){
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Ok |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 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 |
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 |
348 KB |
Ok |
| 8 |
Correct |
0 ms |
348 KB |
Ok |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
77 ms |
43468 KB |
Ok |
| 2 |
Correct |
38 ms |
21716 KB |
Ok |
| 3 |
Correct |
1 ms |
600 KB |
Ok |
| 4 |
Correct |
0 ms |
344 KB |
Ok |
| 5 |
Correct |
0 ms |
348 KB |
Ok |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Ok |
| 2 |
Correct |
2 ms |
1628 KB |
Ok |
| 3 |
Correct |
39 ms |
21828 KB |
Ok |
| 4 |
Correct |
19 ms |
11004 KB |
Ok |
| 5 |
Correct |
1 ms |
344 KB |
Ok |
| 6 |
Correct |
1 ms |
856 KB |
Ok |
| 7 |
Correct |
8 ms |
5816 KB |
Ok |
| 8 |
Correct |
0 ms |
348 KB |
Ok |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
81 ms |
43360 KB |
Ok |
| 2 |
Correct |
78 ms |
43504 KB |
Ok |
| 3 |
Correct |
72 ms |
43464 KB |
Ok |
| 4 |
Correct |
38 ms |
21856 KB |
Ok |
| 5 |
Correct |
37 ms |
21712 KB |
Ok |
| 6 |
Correct |
19 ms |
10976 KB |
Ok |
| 7 |
Correct |
20 ms |
10976 KB |
Ok |
| 8 |
Correct |
8 ms |
5720 KB |
Ok |
| 9 |
Correct |
8 ms |
5720 KB |
Ok |
| 10 |
Correct |
4 ms |
2904 KB |
Ok |
| 11 |
Correct |
1 ms |
604 KB |
Ok |
| 12 |
Correct |
1 ms |
604 KB |
Ok |
| 13 |
Correct |
0 ms |
348 KB |
Ok |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
77 ms |
43468 KB |
Ok |
| 2 |
Correct |
38 ms |
21716 KB |
Ok |
| 3 |
Correct |
1 ms |
600 KB |
Ok |
| 4 |
Correct |
0 ms |
344 KB |
Ok |
| 5 |
Correct |
0 ms |
348 KB |
Ok |
| 6 |
Correct |
0 ms |
344 KB |
Ok |
| 7 |
Correct |
2 ms |
1628 KB |
Ok |
| 8 |
Correct |
39 ms |
21828 KB |
Ok |
| 9 |
Correct |
19 ms |
11004 KB |
Ok |
| 10 |
Correct |
1 ms |
344 KB |
Ok |
| 11 |
Correct |
1 ms |
856 KB |
Ok |
| 12 |
Correct |
8 ms |
5816 KB |
Ok |
| 13 |
Correct |
0 ms |
348 KB |
Ok |
| 14 |
Correct |
81 ms |
43360 KB |
Ok |
| 15 |
Correct |
78 ms |
43504 KB |
Ok |
| 16 |
Correct |
72 ms |
43464 KB |
Ok |
| 17 |
Correct |
38 ms |
21856 KB |
Ok |
| 18 |
Correct |
37 ms |
21712 KB |
Ok |
| 19 |
Correct |
19 ms |
10976 KB |
Ok |
| 20 |
Correct |
20 ms |
10976 KB |
Ok |
| 21 |
Correct |
8 ms |
5720 KB |
Ok |
| 22 |
Correct |
8 ms |
5720 KB |
Ok |
| 23 |
Correct |
4 ms |
2904 KB |
Ok |
| 24 |
Correct |
1 ms |
604 KB |
Ok |
| 25 |
Correct |
1 ms |
604 KB |
Ok |
| 26 |
Correct |
0 ms |
348 KB |
Ok |
| 27 |
Execution timed out |
1064 ms |
348 KB |
Time limit exceeded |
| 28 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1049 ms |
348 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
