oj.uz

Submission #289816

# Submission time Handle Problem Language Result Execution time Memory
289816 2020-09-03T06:03:04 Z Pyqe Snake Escaping (JOI18_snake_escaping) C++14
5 / 100
 2000 ms 65540 KB 
#include <bits/stdc++.h>

using namespace std;

int nd,n,d,d2,p3[11],dh[59049],pst[59049],a[1ll<<20],dp[1ll<<10][59049];

int main()
{
	int t,rr,i,k,w,ww,mk,mkk,z;
	string s;
	
	p3[0]=1;
	for(i=1;i<=10;i++)
	{
		p3[i]=p3[i-1]*3;
	}
	for(mk=0;mk<p3[10];mk++)
	{
		w=0;
		for(i=9;i+1;i--)
		{
			k=mk/p3[i]%3;
			if(k==2)
			{
				break;
			}
			w=w<<1|k;
		}
		dh[mk]=i;
		if(dh[mk]==-1)
		{
			pst[mk]=w;
		}
	}
	scanf("%d%d",&nd,&t);
	n=1ll<<nd;
	d=min(nd,10);
	d2=max(nd-10,0);
	cin>>s;
	for(i=0;i<n;i++)
	{
		a[i]=s[i]-'0';
	}
	for(i=0;i<1ll<<d;i++)
	{
		for(mk=0;mk<p3[d2];mk++)
		{
			if(dh[mk]==-1)
			{
				dp[i][mk]=a[i<<d2|pst[mk]];
			}
			else
			{
				dp[i][mk]=dp[i][mk-p3[dh[mk]]*2]+dp[i][mk-p3[dh[mk]]];
			}
		}
	}
	for(rr=0;rr<t;rr++)
	{
		cin>>s;
		w=0;
		ww=0;
		for(i=0;i<d;i++)
		{
			k=(s[i]=='1')+2*(s[i]=='?');
			w=w<<1|k%2;
			ww=ww<<1|k/2;
		}
		mk=0;
		for(i=0;i<d2;i++)
		{
			k=(s[d+i]=='1')+2*(s[d+i]=='?');
			mk=mk*3+k;
		}
		z=0;
		for(mkk=ww;1;mkk=mkk-1&ww)
		{
			z+=dp[mkk|w][mk];
			if(!mkk)
			{
				break;
			}
		}
		printf("%d\n",z);
	}
}

Compilation message

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:76:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   76 |   for(mkk=ww;1;mkk=mkk-1&ww)
      |                    ~~~^~
snake_escaping.cpp:35:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   35 |  scanf("%d%d",&nd,&t);
      |  ~~~~~^~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5248 KB Output is correct
2 Correct 7 ms 5248 KB Output is correct
3 Correct 7 ms 5248 KB Output is correct
4 Correct 7 ms 5248 KB Output is correct
5 Correct 7 ms 5248 KB Output is correct
6 Correct 7 ms 5120 KB Output is correct
7 Correct 7 ms 5248 KB Output is correct
8 Correct 11 ms 5248 KB Output is correct
9 Correct 8 ms 5248 KB Output is correct
10 Correct 7 ms 5248 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5248 KB Output is correct
2 Correct 7 ms 5248 KB Output is correct
3 Correct 7 ms 5248 KB Output is correct
4 Correct 7 ms 5248 KB Output is correct
5 Correct 7 ms 5248 KB Output is correct
6 Correct 7 ms 5120 KB Output is correct
7 Correct 7 ms 5248 KB Output is correct
8 Correct 11 ms 5248 KB Output is correct
9 Correct 8 ms 5248 KB Output is correct
10 Correct 7 ms 5248 KB Output is correct
11 Execution timed out 2029 ms 15352 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5248 KB Output is correct
2 Correct 7 ms 5248 KB Output is correct
3 Correct 7 ms 5248 KB Output is correct
4 Correct 7 ms 5248 KB Output is correct
5 Correct 7 ms 5248 KB Output is correct
6 Correct 7 ms 5120 KB Output is correct
7 Correct 7 ms 5248 KB Output is correct
8 Correct 11 ms 5248 KB Output is correct
9 Correct 8 ms 5248 KB Output is correct
10 Correct 7 ms 5248 KB Output is correct
11 Execution timed out 2029 ms 15352 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5248 KB Output is correct
2 Correct 7 ms 5248 KB Output is correct
3 Correct 7 ms 5248 KB Output is correct
4 Correct 7 ms 5248 KB Output is correct
5 Correct 7 ms 5248 KB Output is correct
6 Correct 7 ms 5120 KB Output is correct
7 Correct 7 ms 5248 KB Output is correct
8 Correct 11 ms 5248 KB Output is correct
9 Correct 8 ms 5248 KB Output is correct
10 Correct 7 ms 5248 KB Output is correct
11 Runtime error 133 ms 65540 KB Execution killed with signal 9
12 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5248 KB Output is correct
2 Correct 7 ms 5248 KB Output is correct
3 Correct 7 ms 5248 KB Output is correct
4 Correct 7 ms 5248 KB Output is correct
5 Correct 7 ms 5248 KB Output is correct
6 Correct 7 ms 5120 KB Output is correct
7 Correct 7 ms 5248 KB Output is correct
8 Correct 11 ms 5248 KB Output is correct
9 Correct 8 ms 5248 KB Output is correct
10 Correct 7 ms 5248 KB Output is correct
11 Execution timed out 2029 ms 15352 KB Time limit exceeded
12 Halted 0 ms 0 KB -