제출 #58965

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
58965		TadijaSebez	Snake Escaping (JOI18_snake_escaping)	C++11	100 / 100	1522 ms	40724 KiB

snake_escaping

#include <stdio.h>
const int N=1<<20;
int dp0[N],dp1[N],pc[N];
char s[N],t[20];
int min(int a, int b){ return a>b?b:a;}
int abs(int x){ return x>0?x:-x;}
int main()
{
	int n,q,i,mask;
	for(i=1;i<N;i++) pc[i]=pc[i-(i&-i)]+1;
	scanf("%i %i",&n,&q);
	scanf("%s",s);
	for(i=0;i<(1<<n);i++)
	{
		dp1[i]=dp0[((1<<n)-1)^i]=s[i]-'0';
	}
	for(i=0;i<n;i++)
	{
		for(mask=0;mask<(1<<n);mask++)
		{
			if((mask>>i)&1)
			{
				dp1[mask]+=dp1[mask^(1<<i)];
				dp0[mask]+=dp0[mask^(1<<i)];
			}
		}
	}
	while(q--)
	{
		scanf("%s",t);
		int a=0,b=0,c=0;
		for(i=0;i<n;i++)
		{
			if(t[n-i-1]=='0') a+=1<<i;
			else if(t[n-i-1]=='1') b+=1<<i;
			else c+=1<<i;
		}
		int ans=0;
		if(pc[a]<=min(pc[b],pc[c]))
		{
			for(mask=a;;mask=(mask-1)&a)
			{
				//printf("a:%i %i\n",a,mask);
				if((pc[mask]&1)==(pc[a]&1)) ans+=dp0[mask|c];
				else ans-=dp0[mask|c];
				if(!mask) break;
			}
		}
		else if(pc[b]<=min(pc[a],pc[c]))
		{
			for(mask=b;;mask=(mask-1)&b)
			{
				//printf("b:%i %i\n",b,mask);
				if((pc[mask]&1)==(pc[b]&1)) ans+=dp1[mask|c];
				else ans-=dp1[mask|c];
				if(!mask) break;
			}
		}
		else
		{
			for(mask=c;;mask=(mask-1)&c)
			{
				//printf("c:%i %i\n",c,mask);
				ans+=s[mask|b]-'0';
				if(!mask) break;
			}
		}
		printf("%i\n",abs(ans));
	}
	return 0;
}

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

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:11:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i",&n,&q);
  ~~~~~^~~~~~~~~~~~~~~
snake_escaping.cpp:12:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s",s);
  ~~~~~^~~~~~~~
snake_escaping.cpp:30:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s",t);
   ~~~~~^~~~~~~~

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