//#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
void debug_out() { cerr << endl; }
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
cerr << "[" << H << "]";
debug_out(T...);
}
#ifdef dddxxz
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif
#define SZ(s) ((int)s.size())
clock_t startTime;
double getCurrentTime() {
return (double) (clock() - startTime) / CLOCKS_PER_SEC;
}
typedef long long ll;
//mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
const double eps = 0.00001;
const int MOD = 1e9 + 7;
const int INF = 1000000101;
const long long LLINF = 1223372000000000555;
const int N = 1e6 + 4e4;
const int M = 4500;
const int L = 19;
int n, k, t, s;
bool flag[N];
vector<int> ans;
vector<int> good;
bool used[N];
void dfs(int v){
if (ans.size() == (1 << n)) return;
used[v] = true;
ans.push_back(v);
int cnt = 0;
for (int x : good){
if (ans.size() == (1 << n)) return;
int u = x ^ v;
if (!used[u]) dfs(u), cnt++;
}
if (cnt == 0 && (ans.size() != (1 << n) || !flag[s ^ v])){
cout << -1;
exit(0);
}
}
bool check(vector<int> &v){
if (ans.size() != (1 << n)) return false;
for (int i = 1; i < v.size(); i++){
if (!flag[v[i - 1] ^ v[i]]) return false;
}
return (t == 0 || flag[v[0] ^ v.back()]);
}
void solve(int TC) {
cin >> n >> k >> t >> s;
for (int mask = 0; mask < (1 << n); mask++){
if (__builtin_popcount(mask) == k) good.push_back(mask), flag[mask] = true;
}
dfs(s);
if (check(ans)){
cout << ans.size() << endl;
for (int x : ans){
for (int i = n - 1; i >= 0; i--){
cout << ((x & (1 << i)) > 0);
}
cout << endl;
}
} else cout << -1;
}
int main() {
startTime = clock();
ios_base::sync_with_stdio(false);
bool llololcal = false;
#ifdef dddxxz
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
llololcal = true;
#endif
int TC = 1;
//cin >> TC;
for (int test = 1; test <= TC; test++) {
debug(test);
solve(test);
}
if (llololcal) cerr << endl << "Time: " << getCurrentTime() * 1000 << " ms" << endl;
return 0;
}
Compilation message
lyuboyn.cpp: In function 'void dfs(int)':
lyuboyn.cpp:48:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
48 | if (ans.size() == (1 << n)) return;
| ~~~~~~~~~~~^~~~~~~~~~~
lyuboyn.cpp:53:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
53 | if (ans.size() == (1 << n)) return;
| ~~~~~~~~~~~^~~~~~~~~~~
lyuboyn.cpp:58:33: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
58 | if (cnt == 0 && (ans.size() != (1 << n) || !flag[s ^ v])){
| ~~~~~~~~~~~^~~~~~~~~~~
lyuboyn.cpp: In function 'bool check(std::vector<int>&)':
lyuboyn.cpp:66:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
66 | if (ans.size() != (1 << n)) return false;
| ~~~~~~~~~~~^~~~~~~~~~~
lyuboyn.cpp:68:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
68 | for (int i = 1; i < v.size(); i++){
| ~~^~~~~~~~~~
lyuboyn.cpp: In function 'int main()':
lyuboyn.cpp:18:20: warning: statement has no effect [-Wunused-value]
18 | #define debug(...) 42
| ^~
lyuboyn.cpp:110:9: note: in expansion of macro 'debug'
110 | debug(test);
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
364 KB |
Ok |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Ok |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
748 KB |
Ok |
| 2 |
Correct |
9 ms |
11628 KB |
Ok |
| 3 |
Correct |
5 ms |
6248 KB |
Ok |
| 4 |
Correct |
1 ms |
364 KB |
Ok |
| 5 |
Correct |
1 ms |
364 KB |
Ok |
| 6 |
Correct |
1 ms |
364 KB |
Ok |
| 7 |
Correct |
1 ms |
748 KB |
Ok |
| 8 |
Correct |
5 ms |
6156 KB |
Ok |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
869 ms |
27496 KB |
Ok |
| 2 |
Correct |
427 ms |
13804 KB |
Ok |
| 3 |
Correct |
3 ms |
492 KB |
Ok |
| 4 |
Correct |
1 ms |
364 KB |
Ok |
| 5 |
Correct |
1 ms |
364 KB |
Ok |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Ok |
| 2 |
Correct |
25 ms |
1132 KB |
Ok |
| 3 |
Correct |
458 ms |
13804 KB |
Ok |
| 4 |
Correct |
214 ms |
7280 KB |
Ok |
| 5 |
Correct |
2 ms |
364 KB |
Ok |
| 6 |
Correct |
6 ms |
492 KB |
Ok |
| 7 |
Correct |
105 ms |
3948 KB |
Ok |
| 8 |
Correct |
1 ms |
364 KB |
Ok |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
1516 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
869 ms |
27496 KB |
Ok |
| 2 |
Correct |
427 ms |
13804 KB |
Ok |
| 3 |
Correct |
3 ms |
492 KB |
Ok |
| 4 |
Correct |
1 ms |
364 KB |
Ok |
| 5 |
Correct |
1 ms |
364 KB |
Ok |
| 6 |
Correct |
1 ms |
364 KB |
Ok |
| 7 |
Correct |
25 ms |
1132 KB |
Ok |
| 8 |
Correct |
458 ms |
13804 KB |
Ok |
| 9 |
Correct |
214 ms |
7280 KB |
Ok |
| 10 |
Correct |
2 ms |
364 KB |
Ok |
| 11 |
Correct |
6 ms |
492 KB |
Ok |
| 12 |
Correct |
105 ms |
3948 KB |
Ok |
| 13 |
Correct |
1 ms |
364 KB |
Ok |
| 14 |
Runtime error |
4 ms |
1516 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 15 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
620 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
