oj.uz

Submission #348613

# Submission time Handle Problem Language Result Execution time Memory
348613 2021-01-15T09:43:30 Z Nima_Naderi Snake Escaping (JOI18_snake_escaping) C++14
100 / 100
 1583 ms 55264 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
int nd,n,d,d2,p3[13],dh[531441],pst[531441],a[1ll<<20],wg[1000000],wgg[1000000],mka[1000000],dp[531441],sq[1000000];
 
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t,rr,i,k,w,mk;
	string s;
	
	cin>>nd>>t;
	n=1ll<<nd;
	d=min(nd,8);
	d2=max(nd-8,0);
	p3[0]=1;
	for(i=1;i<=d2;i++)
	{
		p3[i]=p3[i-1]*3;
	}
	for(mk=0;mk<p3[d2];mk++)
	{
		w=0;
		for(i=d2-1;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;
		}
	}
	cin>>s;
	for(i=0;i<n;i++)
	{
		a[i]=s[i]-'0';
	}
	for(rr=0;rr<t;rr++)
	{
		cin>>s;
		wg[rr]=0;
		wgg[rr]=0;
		for(i=0;i<d;i++)
		{
			k=(s[i]=='1')+2*(s[i]=='?');
			wg[rr]=wg[rr]<<1|k%2;
			wgg[rr]=wgg[rr]<<1|k<2;
		}
		mka[rr]=0;
		for(i=0;i<d2;i++)
		{
			k=(s[d+i]=='1')+2*(s[d+i]=='?');
			mka[rr]=mka[rr]*3+k;
		}
	}
	for(i=0;i<1ll<<d;i++)
	{
		for(mk=0;mk<p3[d2];mk++)
		{
			if(dh[mk]==-1)
			{
				dp[mk]=a[i<<d2|pst[mk]];
			}
			else
			{
				dp[mk]=dp[mk-p3[dh[mk]]*2]+dp[mk-p3[dh[mk]]];
			}
		}
		for(rr=0;rr<t;rr++)
		{
			if((i&wgg[rr])==wg[rr])
			{
				sq[rr]+=dp[mka[rr]];
			}
		}
	}
	for(rr=0;rr<t;rr++)
	{
		cout<<sq[rr]<<"\n";
	}
}
//codam paride az cms

Compilation message

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:56:24: warning: suggest parentheses around comparison in operand of '|' [-Wparentheses]
   56 |    wgg[rr]=wgg[rr]<<1|k<2;
      |                       ~^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 2 ms 492 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 492 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 2 ms 492 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 735 ms 30956 KB Output is correct
12 Correct 818 ms 30444 KB Output is correct
13 Correct 650 ms 29804 KB Output is correct
14 Correct 690 ms 29804 KB Output is correct
15 Correct 797 ms 30828 KB Output is correct
16 Correct 670 ms 30060 KB Output is correct
17 Correct 675 ms 29932 KB Output is correct
18 Correct 545 ms 31852 KB Output is correct
19 Correct 566 ms 28780 KB Output is correct
20 Correct 815 ms 30444 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 2 ms 492 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 735 ms 30956 KB Output is correct
12 Correct 818 ms 30444 KB Output is correct
13 Correct 650 ms 29804 KB Output is correct
14 Correct 690 ms 29804 KB Output is correct
15 Correct 797 ms 30828 KB Output is correct
16 Correct 670 ms 30060 KB Output is correct
17 Correct 675 ms 29932 KB Output is correct
18 Correct 545 ms 31852 KB Output is correct
19 Correct 566 ms 28780 KB Output is correct
20 Correct 815 ms 30444 KB Output is correct
21 Correct 805 ms 33772 KB Output is correct
22 Correct 826 ms 34028 KB Output is correct
23 Correct 693 ms 33132 KB Output is correct
24 Correct 707 ms 32840 KB Output is correct
25 Correct 875 ms 35052 KB Output is correct
26 Correct 690 ms 33388 KB Output is correct
27 Correct 692 ms 33256 KB Output is correct
28 Correct 542 ms 35820 KB Output is correct
29 Correct 570 ms 31852 KB Output is correct
30 Correct 832 ms 34028 KB Output is correct
31 Correct 681 ms 34028 KB Output is correct
32 Correct 693 ms 33900 KB Output is correct
33 Correct 612 ms 32748 KB Output is correct
34 Correct 734 ms 32876 KB Output is correct
35 Correct 684 ms 33644 KB Output is correct
36 Correct 464 ms 31832 KB Output is correct
37 Correct 737 ms 33900 KB Output is correct
38 Correct 582 ms 31852 KB Output is correct
39 Correct 704 ms 33004 KB Output is correct
40 Correct 713 ms 32876 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 2 ms 492 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 351 ms 13200 KB Output is correct
12 Correct 356 ms 13328 KB Output is correct
13 Correct 370 ms 13072 KB Output is correct
14 Correct 348 ms 13200 KB Output is correct
15 Correct 364 ms 13328 KB Output is correct
16 Correct 348 ms 13200 KB Output is correct
17 Correct 342 ms 13072 KB Output is correct
18 Correct 338 ms 13328 KB Output is correct
19 Correct 336 ms 12944 KB Output is correct
20 Correct 352 ms 13328 KB Output is correct
21 Correct 392 ms 13328 KB Output is correct
22 Correct 344 ms 13200 KB Output is correct
23 Correct 335 ms 13200 KB Output is correct
24 Correct 343 ms 13200 KB Output is correct
25 Correct 349 ms 13200 KB Output is correct
26 Correct 332 ms 13020 KB Output is correct
27 Correct 343 ms 13328 KB Output is correct
28 Correct 339 ms 12944 KB Output is correct
29 Correct 340 ms 13072 KB Output is correct
30 Correct 347 ms 13072 KB Output is correct
31 Correct 341 ms 13088 KB Output is correct
32 Correct 346 ms 13072 KB Output is correct
33 Correct 343 ms 13072 KB Output is correct
34 Correct 338 ms 12944 KB Output is correct
35 Correct 350 ms 13072 KB Output is correct
36 Correct 349 ms 13088 KB Output is correct
37 Correct 358 ms 13088 KB Output is correct
38 Correct 357 ms 13200 KB Output is correct
39 Correct 351 ms 13200 KB Output is correct
40 Correct 358 ms 13184 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 2 ms 492 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 735 ms 30956 KB Output is correct
12 Correct 818 ms 30444 KB Output is correct
13 Correct 650 ms 29804 KB Output is correct
14 Correct 690 ms 29804 KB Output is correct
15 Correct 797 ms 30828 KB Output is correct
16 Correct 670 ms 30060 KB Output is correct
17 Correct 675 ms 29932 KB Output is correct
18 Correct 545 ms 31852 KB Output is correct
19 Correct 566 ms 28780 KB Output is correct
20 Correct 815 ms 30444 KB Output is correct
21 Correct 805 ms 33772 KB Output is correct
22 Correct 826 ms 34028 KB Output is correct
23 Correct 693 ms 33132 KB Output is correct
24 Correct 707 ms 32840 KB Output is correct
25 Correct 875 ms 35052 KB Output is correct
26 Correct 690 ms 33388 KB Output is correct
27 Correct 692 ms 33256 KB Output is correct
28 Correct 542 ms 35820 KB Output is correct
29 Correct 570 ms 31852 KB Output is correct
30 Correct 832 ms 34028 KB Output is correct
31 Correct 681 ms 34028 KB Output is correct
32 Correct 693 ms 33900 KB Output is correct
33 Correct 612 ms 32748 KB Output is correct
34 Correct 734 ms 32876 KB Output is correct
35 Correct 684 ms 33644 KB Output is correct
36 Correct 464 ms 31832 KB Output is correct
37 Correct 737 ms 33900 KB Output is correct
38 Correct 582 ms 31852 KB Output is correct
39 Correct 704 ms 33004 KB Output is correct
40 Correct 713 ms 32876 KB Output is correct
41 Correct 351 ms 13200 KB Output is correct
42 Correct 356 ms 13328 KB Output is correct
43 Correct 370 ms 13072 KB Output is correct
44 Correct 348 ms 13200 KB Output is correct
45 Correct 364 ms 13328 KB Output is correct
46 Correct 348 ms 13200 KB Output is correct
47 Correct 342 ms 13072 KB Output is correct
48 Correct 338 ms 13328 KB Output is correct
49 Correct 336 ms 12944 KB Output is correct
50 Correct 352 ms 13328 KB Output is correct
51 Correct 392 ms 13328 KB Output is correct
52 Correct 344 ms 13200 KB Output is correct
53 Correct 335 ms 13200 KB Output is correct
54 Correct 343 ms 13200 KB Output is correct
55 Correct 349 ms 13200 KB Output is correct
56 Correct 332 ms 13020 KB Output is correct
57 Correct 343 ms 13328 KB Output is correct
58 Correct 339 ms 12944 KB Output is correct
59 Correct 340 ms 13072 KB Output is correct
60 Correct 347 ms 13072 KB Output is correct
61 Correct 341 ms 13088 KB Output is correct
62 Correct 346 ms 13072 KB Output is correct
63 Correct 343 ms 13072 KB Output is correct
64 Correct 338 ms 12944 KB Output is correct
65 Correct 350 ms 13072 KB Output is correct
66 Correct 349 ms 13088 KB Output is correct
67 Correct 358 ms 13088 KB Output is correct
68 Correct 357 ms 13200 KB Output is correct
69 Correct 351 ms 13200 KB Output is correct
70 Correct 358 ms 13184 KB Output is correct
71 Correct 1167 ms 52380 KB Output is correct
72 Correct 1215 ms 52548 KB Output is correct
73 Correct 1164 ms 50960 KB Output is correct
74 Correct 1283 ms 51344 KB Output is correct
75 Correct 1583 ms 53392 KB Output is correct
76 Correct 1368 ms 51600 KB Output is correct
77 Correct 1400 ms 51440 KB Output is correct
78 Correct 915 ms 55264 KB Output is correct
79 Correct 943 ms 49284 KB Output is correct
80 Correct 1255 ms 52420 KB Output is correct
81 Correct 1521 ms 52344 KB Output is correct
82 Correct 1322 ms 51344 KB Output is correct
83 Correct 990 ms 50704 KB Output is correct
84 Correct 1315 ms 51344 KB Output is correct
85 Correct 1390 ms 51544 KB Output is correct
86 Correct 794 ms 49424 KB Output is correct
87 Correct 1195 ms 52324 KB Output is correct
88 Correct 920 ms 49264 KB Output is correct
89 Correct 1229 ms 51044 KB Output is correct
90 Correct 1284 ms 51472 KB Output is correct
91 Correct 995 ms 50532 KB Output is correct
92 Correct 1392 ms 51556 KB Output is correct
93 Correct 1410 ms 51428 KB Output is correct
94 Correct 870 ms 49444 KB Output is correct
95 Correct 1486 ms 51328 KB Output is correct
96 Correct 1502 ms 51428 KB Output is correct
97 Correct 1455 ms 51480 KB Output is correct
98 Correct 1454 ms 51424 KB Output is correct
99 Correct 1513 ms 51436 KB Output is correct
100 Correct 1469 ms 51420 KB Output is correct