Submission #686586

#	Time	Username	Problem	Language	Result	Execution time	Memory
686586		coffee5427	Snake Escaping (JOI18_snake_escaping)	C++17	0 / 100	0 ms	212 KiB

snake_escaping

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN =(1<<20)+5;
bool Sunny;
int L,Q,f[MAXN],A[MAXN],B,C[MAXN],D,g[MAXN];
char S[MAXN],T[25];
bool Small;
ll Ans;
ll solve()
{
	int cnt1=0,cnt0=0,cnt2=0;
	int B=0,D=0,num=0,E=0;
	for(int i=0;i<L;++i)
	{
		num<<=1;B<<=1;D<<=1;E<<=1;
		if(T[i]=='1') ++cnt1,B|=1;
		if(T[i]=='?') ++cnt2,D|=1;
		if(T[i]=='0') ++cnt0,E|=1;
	}
	Ans=0;
	if(cnt2<=6)
	{
		for(int i=0;i<L;++i) num=(num<<1)|(T[i]=='?'||T[i]=='1');
		Ans+=A[num];
		for(int i=D;i;i=(i-1)&D)
			Ans+=A[num^i];
	}
	else if(cnt1<=6)
	{
		for(int i=0;i<L;++i) num=(num<<1)|(T[i]=='1'||T[i]=='?');
		Ans=f[num];
		for(int i=B;i;i=(i-1)&B)
		{
			if(C[i]%2==0) Ans+=f[num^i];
			else Ans-=f[num^i];
		}
	}
	else if(cnt0<=6)
	{
		for(int i=0;i<L;++i) num=(num<<1)|(T[i]=='1');
		Ans=g[num];
		for(int i=E;i;i=(i-1)&E)
		{
			if(C[i]%2==0) Ans+=g[num^i];
			else Ans-=g[num^i];
		}
	}
	return Ans;
}
int main()
{
//	cout<<1.0*(&Small-&Sunny)/1024/1024<<"MB"<<endl;
	freopen("d.in","r",stdin);
	freopen("d.out","w",stdout);
	scanf("%d %d",&L,&Q);
	scanf("%s",S);
	for(int i=0;i<(1<<L);++i) C[i]=__builtin_popcount(i);
	for(int i=0;i<(1<<L);++i) f[i]+=S[i]-'0',A[i]=S[i]-'0',g[i]+=S[i]-'0';
	for(int i=0;i<L;++i)
		for(int j=0;j<(1<<L);++j) if((1<<i)&j) f[j]+=f[j^(1<<i)];
	for(int i=0;i<L;++i)
		for(int j=0;j<(1<<L);++j) if(((1<<i)&j)==0) g[j]+=g[j^(1<<i)];
	while(Q--)
	{
		scanf("%s",T);
		printf("%lld\n",solve());
	}
	return 0;
}

Compilation message (stderr)

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:54:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |  freopen("d.in","r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~
snake_escaping.cpp:55:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |  freopen("d.out","w",stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~
snake_escaping.cpp:56:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |  scanf("%d %d",&L,&Q);
      |  ~~~~~^~~~~~~~~~~~~~~
snake_escaping.cpp:57:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |  scanf("%s",S);
      |  ~~~~~^~~~~~~~
snake_escaping.cpp:66:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |   scanf("%s",T);
      |   ~~~~~^~~~~~~~

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