oj.uz

Submission #340953

# Submission time Handle Problem Language Result Execution time Memory
340953 2020-12-28T17:45:33 Z ogibogi2004 Snake Escaping (JOI18_snake_escaping) C++14
5 / 100
 2000 ms 65540 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 37228 KB Output is correct
2 Correct 78 ms 37248 KB Output is correct
3 Correct 72 ms 37240 KB Output is correct
4 Correct 71 ms 37228 KB Output is correct
5 Correct 75 ms 37388 KB Output is correct
6 Correct 72 ms 37228 KB Output is correct
7 Correct 72 ms 37248 KB Output is correct
8 Correct 72 ms 37356 KB Output is correct
9 Correct 73 ms 37228 KB Output is correct
10 Correct 75 ms 37240 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 37228 KB Output is correct
2 Correct 78 ms 37248 KB Output is correct
3 Correct 72 ms 37240 KB Output is correct
4 Correct 71 ms 37228 KB Output is correct
5 Correct 75 ms 37388 KB Output is correct
6 Correct 72 ms 37228 KB Output is correct
7 Correct 72 ms 37248 KB Output is correct
8 Correct 72 ms 37356 KB Output is correct
9 Correct 73 ms 37228 KB Output is correct
10 Correct 75 ms 37240 KB Output is correct
11 Execution timed out 2084 ms 38788 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 37228 KB Output is correct
2 Correct 78 ms 37248 KB Output is correct
3 Correct 72 ms 37240 KB Output is correct
4 Correct 71 ms 37228 KB Output is correct
5 Correct 75 ms 37388 KB Output is correct
6 Correct 72 ms 37228 KB Output is correct
7 Correct 72 ms 37248 KB Output is correct
8 Correct 72 ms 37356 KB Output is correct
9 Correct 73 ms 37228 KB Output is correct
10 Correct 75 ms 37240 KB Output is correct
11 Execution timed out 2084 ms 38788 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 37228 KB Output is correct
2 Correct 78 ms 37248 KB Output is correct
3 Correct 72 ms 37240 KB Output is correct
4 Correct 71 ms 37228 KB Output is correct
5 Correct 75 ms 37388 KB Output is correct
6 Correct 72 ms 37228 KB Output is correct
7 Correct 72 ms 37248 KB Output is correct
8 Correct 72 ms 37356 KB Output is correct
9 Correct 73 ms 37228 KB Output is correct
10 Correct 75 ms 37240 KB Output is correct
11 Runtime error 195 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 37228 KB Output is correct
2 Correct 78 ms 37248 KB Output is correct
3 Correct 72 ms 37240 KB Output is correct
4 Correct 71 ms 37228 KB Output is correct
5 Correct 75 ms 37388 KB Output is correct
6 Correct 72 ms 37228 KB Output is correct
7 Correct 72 ms 37248 KB Output is correct
8 Correct 72 ms 37356 KB Output is correct
9 Correct 73 ms 37228 KB Output is correct
10 Correct 75 ms 37240 KB Output is correct
11 Execution timed out 2084 ms 38788 KB Time limit exceeded
12 Halted 0 ms 0 KB -