Submission #348613

#	Time	Username	Problem	Language	Result	Execution time	Memory
348613		Nima_Naderi	Snake Escaping (JOI18_snake_escaping)	C++14	100 / 100	1583 ms	55264 KiB

snake_escaping

#include <bits/stdc++.h>
 
using namespace std;
 
int nd,n,d,d2,p3[13],dh[531441],pst[531441],a[1ll<<20],wg[1000000],wgg[1000000],mka[1000000],dp[531441],sq[1000000];
 
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t,rr,i,k,w,mk;
	string s;
	
	cin>>nd>>t;
	n=1ll<<nd;
	d=min(nd,8);
	d2=max(nd-8,0);
	p3[0]=1;
	for(i=1;i<=d2;i++)
	{
		p3[i]=p3[i-1]*3;
	}
	for(mk=0;mk<p3[d2];mk++)
	{
		w=0;
		for(i=d2-1;i+1;i--)
		{
			k=mk/p3[i]%3;
			if(k==2)
			{
				break;
			}
			w=w<<1|k;
		}
		dh[mk]=i;
		if(dh[mk]==-1)
		{
			pst[mk]=w;
		}
	}
	cin>>s;
	for(i=0;i<n;i++)
	{
		a[i]=s[i]-'0';
	}
	for(rr=0;rr<t;rr++)
	{
		cin>>s;
		wg[rr]=0;
		wgg[rr]=0;
		for(i=0;i<d;i++)
		{
			k=(s[i]=='1')+2*(s[i]=='?');
			wg[rr]=wg[rr]<<1|k%2;
			wgg[rr]=wgg[rr]<<1|k<2;
		}
		mka[rr]=0;
		for(i=0;i<d2;i++)
		{
			k=(s[d+i]=='1')+2*(s[d+i]=='?');
			mka[rr]=mka[rr]*3+k;
		}
	}
	for(i=0;i<1ll<<d;i++)
	{
		for(mk=0;mk<p3[d2];mk++)
		{
			if(dh[mk]==-1)
			{
				dp[mk]=a[i<<d2|pst[mk]];
			}
			else
			{
				dp[mk]=dp[mk-p3[dh[mk]]*2]+dp[mk-p3[dh[mk]]];
			}
		}
		for(rr=0;rr<t;rr++)
		{
			if((i&wgg[rr])==wg[rr])
			{
				sq[rr]+=dp[mka[rr]];
			}
		}
	}
	for(rr=0;rr<t;rr++)
	{
		cout<<sq[rr]<<"\n";
	}
}
//codam paride az cms

Compilation message (stderr)

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:56:24: warning: suggest parentheses around comparison in operand of '|' [-Wparentheses]
   56 |    wgg[rr]=wgg[rr]<<1|k<2;
      |                       ~^~

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 10 / 10
• Subtask 4: 53 / 53
• Subtask 5: 25 / 25