Submission #340953

#	Time	Username	Problem	Language	Result	Execution time	Memory
340953		ogibogi2004	Snake Escaping (JOI18_snake_escaping)	C++14	5 / 100	2084 ms	65540 KiB

snake_escaping

#include<bits/stdc++.h>
using namespace std;
const int MAXL=20;
const int MAXN=(1<<20);
int l,q;
int p[MAXN],dp[MAXN];
string binary[MAXN];
int f(string s1,string s2)
{
	int ret=0;
	for(int j=0;j<s2.size();j++)
	{
		if(s1[j]=='0'&&s2[j]=='1')return 0;
		if(s1[j]=='?'&&s2[j]=='0')return 0;
		if(s1[j]=='1'&&s2[j]=='0')ret++;
	}
	return 1-(ret%2)*2;
}
int main()
{
	cin>>l>>q;
	string s;
	for(int i=0;i<(1<<l);i++)
	{
		for(int j=l-1;j>=0;j--)
		{
			if(i&(1<<j))binary[i]+="1";
			else binary[i]+="0";
		}
	}
	cin>>s;
	for(int i=0;i<s.size();i++)
	{
		p[i]=s[i]-'0';
		dp[i]+=p[i];
	}
	for(int i=0;i<MAXL;i++)
	{
		for(int mask=0;mask<MAXN;mask++)
		{
			if(mask&(1<<i))
			{
				dp[mask]+=dp[mask^(1<<i)];
			}
		}
	}
	for(int i=0;i<q;i++)
	{
		string s;
		cin>>s;
		int ans=0;
		for(int j=0;j<(1<<l);j++)
		{
			//cout<<j<<" "<<dp[j]<<" "<<f(s,binary[j])<<" "<<s<<" "<<binary[j]<<endl;
			ans+=dp[j]*f(s,binary[j]);
		}
		cout<<ans<<endl;
	}
return 0;
}

Compilation message (stderr)

snake_escaping.cpp: In function 'int f(std::string, std::string)':
snake_escaping.cpp:11:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |  for(int j=0;j<s2.size();j++)
      |              ~^~~~~~~~~~
snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:32:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |  for(int i=0;i<s.size();i++)
      |              ~^~~~~~~~~

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