#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)
{
int x = node;
for (int i = 0; i < n; i++)
{
x ^= (1 << i);
if (!used[x] and dfs(x, step + 1))
{
ans.push_back(node);
return true;
}
x ^= (1 << i);
}
}
else if (k == 3)
{
int y = node;
for (int i = 0; i < n; i++)
{
y ^= (1 << i);
for (int j = i + 1; j < n; j++)
{
y ^= (1 << j);
for (int x = j + 1; x < n; x++)
{
y ^= (1 << x);
if (!used[y] and dfs(y, step + 1))
{
ans.push_back(node);
return true;
}
y ^= (1 << x);
}
y ^= (1 << j);
}
y ^= (1 << i);
}
}
else if (k == 5)
{
int y = node;
for (int i = 0; i < n; i++)
{
y ^= (1 << i);
for (int j = i + 1; j < n; j++)
{
y ^= (1 << j);
for (int x = j + 1; x < n; x++)
{
y ^= (1 << x);
for (int i1 = x + 1; i1 < n; i1++)
{
y ^= (1 << i1);
for (int i2 = i1 + 1; i2 < n; i2++)
{
y ^= (1 << i2);
if (!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;
}
y ^= (1 << i2);
}
y ^= (1 << i1);
}
y ^= (1 << x);
}
y ^= (1 << j);
}
y ^= (1 << i);
}
}
else if (k == 7)
{
int y = node;
for (int i = 0; i < n; i++)
{
y ^= (1 << i);
for (int j = i + 1; j < n; j++)
{
y ^= (1 << j);
for (int x = j + 1; x < n; x++)
{
y ^= (1 << x);
for (int i1 = x + 1; i1 < n; i1++)
{
y ^= (1 << i1);
for (int i2 = i1 + 1; i2 < n; i2++)
{
y ^= (1 << i2);
for (int i3 = i2 + 1; i3 < n; i3++)
{
y ^= (1 << i3);
for (int i4 = i3 + 1; i4 < n; i4++)
{
y ^= (1 << i4);
if (!used[y] and dfs(y, step + 1))
{
ans.push_back(node);
return true;
}
y ^= (1 << i4);
}
y ^= (1 << i3);
}
y ^= (1 << i2);
}
y ^= (1 << i1);
}
y ^= (1 << x);
}
y ^= (1 << j);
}
y ^= (1 << i);
}
}
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 or k == 9 or n == k or n % 2 == 1)
{
cout << -1;
return;
}
bool flag = 2 * k > n;
if (2 * k > n)
k = n - k;
if (k % 2 == 0)
{
cout << -1;
return;
}
used.resize((1 << n));
if (dfs(sx, 0))
{
cout << (1 << n) << endl;
if (flag)
{
reverse(all(ans));
for (int i = 0; i < ans.size(); i++)
{
str s = "";
if ((i & 1))
{
for (int j = 0; j < n; j++)
{
if (ans[i] % 2 == 0)
s += '1';
else
s += '0';
ans[i] /= 2;
}
cout << s << endl;
}
else
{
for (int j = 0; j < n; j++)
{
if (ans[i] % 2 == 0)
s += '0';
else
s += '1';
ans[i] /= 2;
}
cout << s << endl;
}
}
}
else
{
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:199:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
199 | for (int i = 0; i < ans.size(); i++)
| ~~^~~~~~~~~~~~
lyuboyn.cpp:231:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
231 | for (int i = 0; i < ans.size(); i++)
| ~~^~~~~~~~~~~~
| # |
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 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Ok |
| 2 |
Correct |
0 ms |
384 KB |
Ok |
| 3 |
Correct |
0 ms |
344 KB |
Ok |
| 4 |
Correct |
1 ms |
348 KB |
Ok |
| 5 |
Correct |
0 ms |
348 KB |
Ok |
| 6 |
Correct |
1 ms |
348 KB |
Ok |
| 7 |
Correct |
0 ms |
348 KB |
Ok |
| 8 |
Correct |
0 ms |
348 KB |
Ok |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
71 ms |
35112 KB |
Ok |
| 2 |
Incorrect |
0 ms |
348 KB |
Output -1 while solution exists |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output -1 while solution exists |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
77 ms |
35128 KB |
Ok |
| 2 |
Correct |
76 ms |
35224 KB |
Ok |
| 3 |
Correct |
69 ms |
35344 KB |
Ok |
| 4 |
Incorrect |
0 ms |
344 KB |
Output -1 while solution exists |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
71 ms |
35112 KB |
Ok |
| 2 |
Incorrect |
0 ms |
348 KB |
Output -1 while solution exists |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output -1 while solution exists |
| 2 |
Halted |
0 ms |
0 KB |
- |
