This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("-O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define fi first
#define se second
#define p_b push_back
#define pll pair<ll,ll>
#define pii pair<int,int>
#define m_p make_pair
#define all(x) x.begin(),x.end()
#define sset ordered_set
#define sqr(x) (x)*(x)
#define pw(x) (1ll << x)
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
const ll MAXN = 1123456;
const ll N = 2e5;
mt19937_64 rnd(chrono::system_clock::now().time_since_epoch().count());
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename T> void vout(T s){cout << s << endl;exit(0);}
ll Val(string s){
ll ans = 0;
for(auto i : s){
ans *= 2;
ans |= i - '0';
}
return ans;
}
ll n;
string Fst(ll x){
string ans;
for(int i = n - 1; i >= 0; i--){
if((x & pw(i))){
ans += "1";
}else ans += "0";
}
return ans;
}
ll kol(ll a, ll b){
ll ans = 0;
for(int i = 0; i < n; i++){
if((a & pw(i)) != (b & pw(i)))ans++;
}
return ans;
}
bool f[MAXN];
ll t, k;
vector <ll> a, c;
void dfs(ll x){
if(clock() / (double)CLOCKS_PER_SEC > 0.95)vout(-1);
f[x] = 1;
a.p_b(x);
if(a.size() == pw(n)){
if(t == 0 || (t == 1 && kol(a.back(), a[0]) == k)){
cout << a.size() << "\n";
for(auto i : a)cout << Fst(i) << "\n";
exit(0);
}
a.pop_back();
}else{
for(auto i : c){
if(f[x ^ i])continue;
dfs(x ^ i);
if(rnd() % 63 == 17)break;
}
}
a.pop_back();
f[x] = 0;
}
int main(){
ios_base :: sync_with_stdio(0);
cin.tie(0);
cin >> n >> k >> t;
vector <ll> a(pw(n));
for(int i = 0; i < pw(n); i++)a[i] = i;
string st;
cin >> st;
ll s = Val(st);
for(int i = 0; i < pw(n); i++)if(__builtin_popcount(i) == k)c.p_b(i);
shuffle(all(c), rnd);
dfs(s);
return 0;
}
Compilation message (stderr)
lyuboyn.cpp: In function 'void dfs(ll)':
lyuboyn.cpp:71:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(a.size() == pw(n)){
^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |