#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
typedef long long ll;
const ll inf=1e15;
#define pb push_back
const int INF=(0x3f3f3f3f);
int tod(vector<int>a){
int res=0;
reverse(a.begin(),a.end());
for(int i=0;i<a.size();i++){
res+=a[i]*(1<<i);
}
return res;
}
int tod(string s){
int res=0;
reverse(s.begin(),s.end());
for(int i=0;i<s.size();i++){
res+=(s[i]-'0')*(1<<i);
}
return res;
}
string tobin(int x,int h){
string res="";
if(x==0){
res="0";
while(res.size()<h)res+="0";
return res;
}
while(x){
if(x%2)res+="1";
else res+="0";
x/=2;
}
while(res.size()<h)res+="0";
reverse(res.begin(),res.end());
return res;
}
void print(vector<int> a){
for(int i=0;i<a.size();i++)cout<<a[i]<<' ';
cout << '\n';
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int n,k,t;
cin>>n>>k>>t;
string s;
cin>>s;
if(k%2==0){
cout<<"-1\n";
return 0;
}
vector<int> a(n,0);
for(int i=0;i<k;i++)a[i]=1;
int start=tod(s);
vector<int>tv;
tv.pb(start);
int X=0;
set<int>st;
st.insert(tod(s));
vector<int>b=a;
int tmp=0;
vector<int> g;
if(t==1){
g.pb(start^tod(a));
st.insert(start^tod(a));
}
while(tv.size()+g.size()<(1<<n)){
bool ok=false;
do{
if(st.find(start^tod(a))!=st.end())continue;
tv.pb(start^tod(a));
st.insert(start^tod(a));
start^=tod(a);
if(tv.size()+g.size()==(1<<n)){ok=true;break;}
//cerr<<tv.size()<<'\n';
}while(prev_permutation(a.begin(),a.end()));
do{
if(st.find(start^tod(b))!=st.end())continue;
tv.pb(start^tod(b));
st.insert(start^tod(b));
start^=tod(b);
if(tv.size()+g.size()==(1<<n)){ok=true;break;}
//cerr<<tv.size()<<'\n';
}while(next_permutation(b.begin(),b.end()));
X++;
if(ok)break;
for(int i=0;i<n;i++)a[i]=0,b[i]=0;
for(int i=0;i<k;i++)a[i]=1,b[i]=1;;
if(tmp==tv.size()){
cout<<"-1\n";
return 0;
}
tmp=tv.size();
prev_permutation(b.begin(),b.end());
//cerr<<tv.size()<<'\n';
}
cout<<(1<<n)<<'\n';
for(int i=0;i<min((1<<n),(int)tv.size());i++){
cout<<tobin(tv[i],n)<<'\n';
//cout<<tv[i]<<'\n';
}
for(int i=0;i<g.size();i++){
cout<<tobin(g[i],n)<<'\n';
}
}
Compilation message
lyuboyn.cpp: In function 'int tod(std::vector<int>)':
lyuboyn.cpp:13:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<a.size();i++){
~^~~~~~~~~
lyuboyn.cpp: In function 'int tod(std::__cxx11::string)':
lyuboyn.cpp:22:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<s.size();i++){
~^~~~~~~~~
lyuboyn.cpp: In function 'std::__cxx11::string tobin(int, int)':
lyuboyn.cpp:32:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(res.size()<h)res+="0";
~~~~~~~~~~^~
lyuboyn.cpp:40:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(res.size()<h)res+="0";
~~~~~~~~~~^~
lyuboyn.cpp: In function 'void print(std::vector<int>)':
lyuboyn.cpp:46:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<a.size();i++)cout<<a[i]<<' ';
~^~~~~~~~~
lyuboyn.cpp: In function 'int main()':
lyuboyn.cpp:77:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(tv.size()+g.size()<(1<<n)){
~~~~~~~~~~~~~~~~~~^~~~~~~
lyuboyn.cpp:84:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(tv.size()+g.size()==(1<<n)){ok=true;break;}
~~~~~~~~~~~~~~~~~~^~~~~~~~
lyuboyn.cpp:92:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(tv.size()+g.size()==(1<<n)){ok=true;break;}
~~~~~~~~~~~~~~~~~~^~~~~~~~
lyuboyn.cpp:99:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(tmp==tv.size()){
~~~^~~~~~~~~~~
lyuboyn.cpp:112:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<g.size();i++){
~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Ok |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Ok |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
380 KB |
Ok |
| 2 |
Correct |
2 ms |
376 KB |
Ok |
| 3 |
Correct |
2 ms |
376 KB |
Ok |
| 4 |
Correct |
2 ms |
380 KB |
Ok |
| 5 |
Correct |
2 ms |
376 KB |
Ok |
| 6 |
Correct |
2 ms |
376 KB |
Ok |
| 7 |
Correct |
2 ms |
376 KB |
Ok |
| 8 |
Correct |
2 ms |
376 KB |
Ok |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
163 ms |
8428 KB |
Output -1 while solution exists |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output -1 while solution exists |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1030 ms |
13824 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
163 ms |
8428 KB |
Output -1 while solution exists |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
182 ms |
6600 KB |
Output -1 while solution exists |
| 2 |
Halted |
0 ms |
0 KB |
- |
