제출 #289816

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
289816		Pyqe	Snake Escaping (JOI18_snake_escaping)	C++14	5 / 100	2029 ms	65540 KiB

snake_escaping

#include <bits/stdc++.h>

using namespace std;

int nd,n,d,d2,p3[11],dh[59049],pst[59049],a[1ll<<20],dp[1ll<<10][59049];

int main()
{
	int t,rr,i,k,w,ww,mk,mkk,z;
	string s;
	
	p3[0]=1;
	for(i=1;i<=10;i++)
	{
		p3[i]=p3[i-1]*3;
	}
	for(mk=0;mk<p3[10];mk++)
	{
		w=0;
		for(i=9;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;
		}
	}
	scanf("%d%d",&nd,&t);
	n=1ll<<nd;
	d=min(nd,10);
	d2=max(nd-10,0);
	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;
			}
		}
		printf("%d\n",z);
	}
}

컴파일 시 표준 에러 (stderr) 메시지

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:76:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   76 |   for(mkk=ww;1;mkk=mkk-1&ww)
      |                    ~~~^~
snake_escaping.cpp:35:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   35 |  scanf("%d%d",&nd,&t);
      |  ~~~~~^~~~~~~~~~~~~~~

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