Submission #331997

#	Time	Username	Problem	Language	Result	Execution time	Memory
331997		arnold518	Snake Escaping (JOI18_snake_escaping)	C++14	100 / 100	1507 ms	59884 KiB

snake_escaping

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXL = 20;
const int MAXN = (1<<MAXL);
const int MAXQ = 1e6;

int L, Q, N;
char SS[MAXN+10], TT[MAXL+10];
int S[MAXN+10], T[MAXL+10];
int dp1[MAXN+10][2], dp2[MAXN+10][2];
int P1[MAXN+10], P2[MAXN+10];

int main()
{
	scanf("%d%d", &L, &Q);
	scanf(" %s", SS);
	N=(1<<L);
	for(int i=0; i<N; i++)
	{
		S[i]=SS[i]-'0';
	}

	for(int i=0; i<(1<<L); i++)
	{
		dp1[i][0]=S[i];
	}

	for(int i=1; i<=L; i++)
	{
		for(int j=0; j<(1<<L); j++)
		{
			dp1[j][i&1]=dp1[j][i-1&1];
			if(j&(1<<(i-1))) dp1[j][i&1]+=dp1[j^(1<<(i-1))][i-1&1];
		}
	}
	for(int i=0; i<(1<<L); i++) P1[i]=dp1[i][L&1];

	for(int i=0; i<(1<<L); i++)
	{
		dp2[i][0]=S[i^((1<<L)-1)];
	}

	for(int i=1; i<=L; i++)
	{
		for(int j=0; j<(1<<L); j++)
		{
			dp2[j][i&1]=dp2[j][i-1&1];
			if(j&(1<<(i-1))) dp2[j][i&1]+=dp2[j^(1<<(i-1))][i-1&1];
		}
	}

	for(int i=0; i<(1<<L); i++) P2[i]=dp2[i^((1<<L)-1)][L&1];

	while(Q--)
	{
		scanf(" %s", TT);
		int cnt0=0, cnt1=0, cnt2=0;
		for(int i=0; i<L; i++)
		{
			if(TT[L-1-i]=='?') T[i]=-1, cnt2++;
			else if(TT[L-1-i]=='0') T[i]=0, cnt0++;
			else if(TT[L-1-i]=='1') T[i]=1, cnt1++;
		}
		int val=min({cnt2, cnt0, cnt1});

		int ans=0;
		if(val==cnt2)
		{
			int m1=0, m2=0;
			for(int i=0; i<L; i++)
			{
				if(T[i]!=-1) m1|=(T[i]<<i);
				else m2|=(1<<i);
			}
			for(int i=m2; ; i=m2&(i-1))
			{
				ans+=S[i|m1];
				if(i==0) break;
			}
		}
		else if(val==cnt1)
		{
			int m0=0, m1=0;
			for(int i=0; i<L; i++)
			{
				if(T[i]==0) m0|=(1<<i);
				if(T[i]==1) m1|=(1<<i);
			}
			for(int i=m1; ; i=m1&(i-1))
			{
				int mask=i|m0;
				mask=mask^((1<<L)-1);
				if(__builtin_popcount(i)%2) ans-=P1[mask];
				else ans+=P1[mask];
				if(i==0) break; 
			}
		}
		else
		{
			int m0=0, m1=0;
			for(int i=0; i<L; i++)
			{
				if(T[i]==0) m0|=(1<<i);
				if(T[i]==1) m1|=(1<<i);
			}
			for(int i=m0; ; i=m0&(i-1))
			{
				int mask=i|m1;
				if(__builtin_popcount(i)%2) ans-=P2[mask];
				else ans+=P2[mask];
				if(i==0) break; 
			}
		}
		printf("%d\n", ans);
	}
}

Compilation message (stderr)

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:37:24: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   37 |    dp1[j][i&1]=dp1[j][i-1&1];
      |                       ~^~
snake_escaping.cpp:38:53: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   38 |    if(j&(1<<(i-1))) dp1[j][i&1]+=dp1[j^(1<<(i-1))][i-1&1];
      |                                                    ~^~
snake_escaping.cpp:52:24: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   52 |    dp2[j][i&1]=dp2[j][i-1&1];
      |                       ~^~
snake_escaping.cpp:53:53: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   53 |    if(j&(1<<(i-1))) dp2[j][i&1]+=dp2[j^(1<<(i-1))][i-1&1];
      |                                                    ~^~
snake_escaping.cpp:20:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   20 |  scanf("%d%d", &L, &Q);
      |  ~~~~~^~~~~~~~~~~~~~~~
snake_escaping.cpp:21:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   21 |  scanf(" %s", SS);
      |  ~~~~~^~~~~~~~~~~
snake_escaping.cpp:61:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   61 |   scanf(" %s", TT);
      |   ~~~~~^~~~~~~~~~~

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