oj.uz

Submission #340958

# Submission time Handle Problem Language Result Execution time Memory
340958 2020-12-28T18:15:03 Z ogibogi2004 Snake Escaping (JOI18_snake_escaping) C++14
0 / 100
 26 ms 33280 KB 
#include<bits/stdc++.h>
using namespace std;
const int MAXL=20;
const int MAXN=(1<<20);
int l,q;
int p[MAXN],dp0[MAXN],dp1[MAXN];
string binary[MAXN];
int f1(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 f0(string s1,string s2)
{
	int ret=0;
	for(int j=0;j<s2.size();j++)
	{
		if(s1[j]=='1'&&s2[j]=='0')return 0;
		if(s1[j]=='?'&&s2[j]=='1')return 0;
		if(s1[j]=='0'&&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';
		dp1[i]+=p[i];
		dp0[i]+=p[i];
	}
	for(int i=0;i<l;i++)
	{
		for(int mask=0;mask<(1<<l);mask++)
		{
			if(mask&(1<<i))
			{
				dp1[mask]+=dp1[mask^(1<<i)];
			}
		}
	}
	for(int i=0;i<l;i++)
	{
		for(int mask=0;mask<(1<<l);mask++)
		{
			if(!(mask&(1<<i)))
			{
				dp0[mask]+=dp0[mask^(1<<i)];
			}
		}
	}
	//cout<<dp0[0]<<" "<<dp1[(1<<l)-1]<<endl;
	//cout<<dp1[0]<<" "<<dp0[(1<<l)-1]<<endl;
	for(int i=0;i<q;++i)
	{
		string s;
		cin>>s;
		int cnt1=0,cnt0=0;
		for(int j=0;j<s.size();j++)
		{
			if(s[j]=='1')cnt1++;
			if(s[j]=='0')cnt0++;
		}
		if(cnt1<=cnt0)
		{
			vector<int>ok;
			ok.push_back(0);
			for(int j=0;j<s.size();++j)
			{
				if(s[j]=='?')
				{
					for(int l=0;l<ok.size();++l)
					{
						ok[l]=ok[l]*2+1;
					}
				}
				else if(s[j]=='0')
				{
					for(int l=0;l<ok.size();++l)
					{
						ok[l]=ok[l]*2;
					}
				}
				else
				{
					int sz=ok.size();
					for(int l=0;l<sz;l++)
					{
						ok[l]=ok[l]*2;
						ok.push_back(ok[l]+1);
					}
				}
			}
			int ans=0;
			for(int j=0;j<ok.size();j++)
			{
				ans+=dp1[ok[j]]*f1(s,binary[ok[j]]);
			}
			cout<<ans<<endl;
		}
		else
		{
			vector<int>ok;
			ok.push_back(0);
			for(int j=0;j<s.size();++j)
			{
				if(s[j]=='?')
				{
					for(int l=0;l<ok.size();++l)
					{
						ok[l]=ok[l]*2;
					}
				}
				else if(s[j]=='1')
				{
					for(int l=0;l<ok.size();++l)
					{
						ok[l]=ok[l]*2+1;
					}
				}
				else
				{
					int sz=ok.size();
					for(int l=0;l<sz;l++)
					{
						ok[l]=ok[l]*2;
						ok.push_back(ok[l]+1);
					}
				}
			}
			int ans=0;
			for(int j=0;j<ok.size();j++)
			{
				//cout<<ok[j]<<" "<<dp0[ok[j]]<<" "<<f0(s,binary[ok[j]])<<" "<<s<<" "<<binary[ok[j]]<<endl;
				ans+=dp0[ok[j]]*f0(s,binary[ok[j]]);
			}
			cout<<ans<<endl;
		}
	}
return 0;
}

Compilation message

snake_escaping.cpp: In function 'int f1(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 f0(std::string, std::string)':
snake_escaping.cpp:22:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |  for(int j=0;j<s2.size();j++)
      |              ~^~~~~~~~~~
snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:43:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |  for(int i=0;i<s.size();i++)
      |              ~^~~~~~~~~
snake_escaping.cpp:76:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |   for(int j=0;j<s.size();j++)
      |               ~^~~~~~~~~
snake_escaping.cpp:85:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |    for(int j=0;j<s.size();++j)
      |                ~^~~~~~~~~
snake_escaping.cpp:89:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |      for(int l=0;l<ok.size();++l)
      |                  ~^~~~~~~~~~
snake_escaping.cpp:96:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |      for(int l=0;l<ok.size();++l)
      |                  ~^~~~~~~~~~
snake_escaping.cpp:112:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |    for(int j=0;j<ok.size();j++)
      |                ~^~~~~~~~~~
snake_escaping.cpp:122:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |    for(int j=0;j<s.size();++j)
      |                ~^~~~~~~~~
snake_escaping.cpp:126:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |      for(int l=0;l<ok.size();++l)
      |                  ~^~~~~~~~~~
snake_escaping.cpp:133:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |      for(int l=0;l<ok.size();++l)
      |                  ~^~~~~~~~~~
snake_escaping.cpp:149:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 |    for(int j=0;j<ok.size();j++)
      |                ~^~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 33152 KB Output is correct
2 Correct 26 ms 33280 KB Output is correct
3 Correct 26 ms 33132 KB Output is correct
4 Correct 26 ms 33132 KB Output is correct
5 Incorrect 25 ms 33260 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 33152 KB Output is correct
2 Correct 26 ms 33280 KB Output is correct
3 Correct 26 ms 33132 KB Output is correct
4 Correct 26 ms 33132 KB Output is correct
5 Incorrect 25 ms 33260 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 33152 KB Output is correct
2 Correct 26 ms 33280 KB Output is correct
3 Correct 26 ms 33132 KB Output is correct
4 Correct 26 ms 33132 KB Output is correct
5 Incorrect 25 ms 33260 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 33152 KB Output is correct
2 Correct 26 ms 33280 KB Output is correct
3 Correct 26 ms 33132 KB Output is correct
4 Correct 26 ms 33132 KB Output is correct
5 Incorrect 25 ms 33260 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 33152 KB Output is correct
2 Correct 26 ms 33280 KB Output is correct
3 Correct 26 ms 33132 KB Output is correct
4 Correct 26 ms 33132 KB Output is correct
5 Incorrect 25 ms 33260 KB Output isn't correct
6 Halted 0 ms 0 KB -