Submission #3234949

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define sqr(x) ((x)*(x))
#define mp make_pair
#define uint unsigned
#define ld long double
#define PI pair<int,int>
inline char gc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
#define gc getchar
inline ll read(){
	ll x = 0; char ch = gc(); bool positive = 1;
	for (; !isdigit(ch); ch = gc())	if (ch == '-')	positive = 0;
	for (; isdigit(ch); ch = gc())	x = x * 10 + ch - '0';
	return positive ? x : -x;
}
inline void write(ll a){
    if(a<0){
    	a=-a; putchar('-');
	}
    if(a>=10)write(a/10);
    putchar('0'+a%10);
}
inline void writeln(ll a){write(a); puts("");}
inline void wri(ll a){write(a); putchar(' ');}
inline ull rnd(){
	return ((ull)rand()<<30^rand())<<4|rand()%4;
}
const int N=22,M=1<<21|5;
int n,k,dp[N][M],ycl[M],Ans[M];
char ch[M];
inline int lowbit(int x){
	return x&(-x);
}
int rev(int x,int len){
	for(int i=0;i<len/2;i++){
		int a=x>>i&1,b=x>>(len-i-1)&1;
		x^=(a^b)<<i; x^=(a^b)<<(len-i-1);
	}
	return x;
}
signed main(){
	n=read(); k=read();
	for(int i=0;i<=n;i++){
		scanf("%s",ch);
		for(int j=0;j<(1<<i);j++)dp[0][(1<<i)+j]+=ch[j]-'0';
	}
	for(int i=2;i<(1<<(n+1));i++)ycl[i]=ycl[i>>1]+1;
	for(int i=0;i<n;i++){
		for(int j=1<<(i+1);j<(1<<(n+1));j++)if(dp[i][j]){
			//cout<<i<<" "<<j<<" "<<dp[i][j]<<endl;
			int len=ycl[j],t=j-(1<<len),k=t>>i;
			if(j>>i&1){
				dp[i+1][j]+=dp[i][j];
				//if(i==0&&j==13)cout<<k<<" "<<(k>>ycl[lowbit(k^((1<<len)-1))]|(t&((1<<i)-1)))<<endl;
				if(k^((1<<(len-i))-1))dp[i+1][(1<<(len-ycl[lowbit(k^((1<<(len-i))-1))]))+((k>>ycl[lowbit(k^((1<<(len-i))-1))])<<i|(t&((1<<i)-1)))]+=dp[i][j];
			}else{
				dp[i+1][j]+=dp[i][j];
				//if(i==1&&j==12)cout<<k<<" "<<(1<<(len-ycl[lowbit(k)]))+(k>>ycl[lowbit(k)]|(t&((1<<i)-1)))<<endl;
				if(k)dp[i+1][(1<<(len-ycl[lowbit(k)]))+((k>>ycl[lowbit(k)])<<i|(t&((1<<i)-1)))]+=dp[i][j];
			}
		}
	}
	for(int i=0;i<=n;i++){
		for(int j=1<<i;j<(1<<(n+1));j++){
			int t=j-(1<<ycl[j]);
			Ans[(1<<i)+(t&((1<<i)-1))]+=dp[i][j];
		}
	}
	//cout<<dp[1][6]<<" "<<dp[2][6]<<" "<<dp[2][10]<<" "<<dp[2][14]<<" "<<Ans[6]<<endl;
	for(int i=(1<<(n+1))-1;i;i--)if(Ans[i]>=k){
		for(int j=1<<ycl[i];j<(1<<(ycl[i]+1));j++){
			int jj=j-(1<<ycl[j]),t=rev(jj,ycl[j]);
			if(Ans[t+(1<<ycl[j])]>=k){
				for(int o=0;o<ycl[j];o++)write(jj>>o&1); return 0;
			}
		}
	}
}
/*
3 3
1
01
1011
01001110


*/

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:49:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s",ch);
                 ^

Judge Result