Submission #168294

#	Time	Username	Problem	Language	Result	Execution time	Memory
168294		Nordway	"The Lyuboyn" code (IZhO19_lyuboyn)	C++14	100 / 100	307 ms	20996 KiB

lyuboyn

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define x first
#define y second
#define pb push_back
#define mp make_pair
#define all(v) v.begin(),v.end()
#define sz(v) (int)v.size()
#define up_b upper_bound
#define low_b lower_bound
#define nl '\n'

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;

typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;

const int N=19;
const int M=1e6+11;
const int inf=1e9;
const ll INF=1e18;
const ll mod=1e9+7;
const double EPS=1e-9;

vector<int>v;
int used[(1<<N)];
int p[(1<<N)];
int a;
int n,k,t;

void answer(int val){
  vector<int>ans;
  while(val!=a){
    ans.pb(val);
    val=p[val];
  }
  ans.pb(a);
  reverse(all(ans));
  cout<<sz(ans)<<nl;
  for(int i=0;i<sz(ans);i++){
    for(int j=n-1;j>=0;j--){
      cout<<((ans[i]>>j)&1);
    }
    cout<<nl;
  }
  exit(0);
}

void go(int val,int i){
  if(i==(1<<n)){
    if(t==1){
      if(__builtin_popcount(a^val)==k){
        answer(val);
      }
    }
    else{
      answer(val);
    }
    return ;
  }
  for(int j=0;j<sz(v);j++){
    int to=(v[j]^val);
    if(!used[to]){
      used[to]=1;
      p[to]=val;
      go(to,i+1);
      used[to]=0;
    }
  }
}

int main(){
  cin>>n>>k>>t;
  string s;
  cin>>s;
  reverse(all(s));
  for(int i=0;i<sz(s);i++){
    a+=(1<<i)*(s[i]-'0');
  }
  for(int i=0;i<(1<<n);i++){
    if(__builtin_popcount(i)==k){
      v.pb(i);
    }
  }
  if(k%2==0)cout<<"-1";
  else{
    used[a]=1;
    go(a,1);
  }
}

• Subtask 1: 0 / 0
• Subtask 2: 5 / 5
• Subtask 3: 3 / 3
• Subtask 4: 11 / 11
• Subtask 5: 15 / 15
• Subtask 6: 18 / 18
• Subtask 7: 31 / 31
• Subtask 8: 17 / 17