Submission #289822

#	Time	Username	Problem	Language	Result	Execution time	Memory
289822		Pyqe	Snake Escaping (JOI18_snake_escaping)	C++14	22 / 100	1076 ms	65540 KiB

snake_escaping

#include <bits/stdc++.h>

using namespace std;

int nd,n,d,d2,p3[12],dh[177147],pst[177147],a[1ll<<20],dp[1ll<<9][177147];

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t,rr,i,k,w,ww,mk,mkk,z;
	string s;
	
	cin>>nd>>t;
	n=1ll<<nd;
	d=min(nd,9);
	d2=max(nd-9,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(i=0;i<1ll<<d;i++)
	{
		for(mk=0;mk<p3[d2];mk++)
		{
			if(dh[mk]==-1)
			{
				dp[i][mk]=a[i<<d2|pst[mk]];
			}
			else
			{
				dp[i][mk]=dp[i][mk-p3[dh[mk]]*2]+dp[i][mk-p3[dh[mk]]];
			}
		}
	}
	for(rr=0;rr<t;rr++)
	{
		cin>>s;
		w=0;
		ww=0;
		for(i=0;i<d;i++)
		{
			k=(s[i]=='1')+2*(s[i]=='?');
			w=w<<1|k%2;
			ww=ww<<1|k/2;
		}
		mk=0;
		for(i=0;i<d2;i++)
		{
			k=(s[d+i]=='1')+2*(s[d+i]=='?');
			mk=mk*3+k;
		}
		z=0;
		for(mkk=ww;1;mkk=mkk-1&ww)
		{
			z+=dp[mkk|w][mk];
			if(!mkk)
			{
				break;
			}
		}
		cout<<z<<"\n";
	}
}

Compilation message (stderr)

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:79:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   79 |   for(mkk=ww;1;mkk=mkk-1&ww)
      |                    ~~~^~

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