oj.uz

Submission #548478

# Submission time Handle Problem Language Result Execution time Memory
548478 2022-04-13T14:03:53 Z MilosMilutinovic Snake Escaping (JOI18_snake_escaping) C++14
75 / 100
 2000 ms 42884 KB 
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=(1<<20)+5;
const int M=1594327;
const int Q=1000050;
int l,n,q,a[N],lst[M],pw[20],ans[Q],dp[M],msk[N],qmask[Q],omask[Q],qv[Q];
char s[N],qs[25];
void calc(){
	pw[0]=1;
	for(int i=1;i<14;i++)pw[i]=pw[i-1]*3;
	for(int i=0;i<M;i++){
		vector<int> bits;
		int x=i;
		while(x>0)bits.push_back(x%3),x/=3;
		lst[i]=-1;
		for(int j=0;j<bits.size();j++)if(bits[j]==2)lst[i]=j;
	}
}
void BruteForce(){
	memset(dp,0,sizeof *dp);
	for(int i=0;i<n;i++){
		int sum=0,x=i,b=0;
		while(x>0)sum+=(x%2)*pw[b++],x/=2;
		dp[sum]+=(int)(s[i]-'0');
	}
	for(int i=0;i<M;i++)if(lst[i]!=-1){
		dp[i]+=dp[i-2*pw[lst[i]]];
		dp[i]+=dp[i-pw[lst[i]]];
	}
	while(q--){
		scanf("%s",qs);
		int sum=0;
		for(int i=0;i<l;i++)sum+=(qs[i]=='0'?0:(qs[i]=='1'?1:2))*pw[l-i-1];
		printf("%i\n",dp[sum]);
	}
}
int main(){
	scanf("%i%i",&l,&q);
	scanf("%s",s);
	n=(1<<l),calc();
	for(int i=0;i<n;i++)a[i]=(int)(s[i]-'0');
	if(l<=13){
		BruteForce();
		return 0;
	}
	for(int i=0;i<n;i++){
		vector<int> bits;
		int x=i;
		while(x>0)bits.pb(x%2),x/=2;
		while(bits.size()<l)bits.pb(0);
		reverse(bits.begin(),bits.end());
		msk[i]=0;
		for(int j=7;j<l;j++)msk[i]+=bits[j]*pw[j-7];
	}
	for(int i=1;i<=q;i++){
		scanf("%s",qs);
		qv[i]=0;
		for(int j=7;j<l;j++)qv[i]+=(qs[j]=='0'?0:(qs[j]=='1'?1:2))*pw[j-7];
		qmask[i]=0;
		for(int b=0;b<7;b++)if(qs[b]!='0')qmask[i]+=(1<<(6-b));
		for(int b=0;b<7;b++)if(qs[b]=='1')omask[i]+=(1<<(6-b));
	}
	int nsz=(1<<(l-7));
	for(int i=0;i<128;i++){
		memset(dp,0,M*sizeof *dp);
		for(int j=0;j<nsz;j++)dp[msk[(i<<(l-7))+j]]+=a[(i<<(l-7))+j];
		for(int j=0;j<M;j++)if(lst[j]!=-1){
			dp[j]+=dp[j-2*pw[lst[j]]];
			dp[j]+=dp[j-pw[lst[j]]];
		}
		for(int j=1;j<=q;j++)if((qmask[j]&i)==i&&(omask[j]|i)==i)ans[j]+=dp[qv[j]];
	}
	for(int i=1;i<=q;i++)printf("%i\n",ans[i]);
	return 0;
}

Compilation message

snake_escaping.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 | #pragma GCC optimization ("O3")
      | 
snake_escaping.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("unroll-loops")
      | 
snake_escaping.cpp: In function 'void calc()':
snake_escaping.cpp:20:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |   for(int j=0;j<bits.size();j++)if(bits[j]==2)lst[i]=j;
      |               ~^~~~~~~~~~~~
snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:54:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   54 |   while(bits.size()<l)bits.pb(0);
      |         ~~~~~~~~~~~^~
snake_escaping.cpp: In function 'void BruteForce()':
snake_escaping.cpp:35:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |   scanf("%s",qs);
      |   ~~~~~^~~~~~~~~
snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:42:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |  scanf("%i%i",&l,&q);
      |  ~~~~~^~~~~~~~~~~~~~
snake_escaping.cpp:43:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |  scanf("%s",s);
      |  ~~~~~^~~~~~~~
snake_escaping.cpp:60:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |   scanf("%s",qs);
      |   ~~~~~^~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 12748 KB Output is correct
2 Correct 265 ms 12808 KB Output is correct
3 Correct 264 ms 12796 KB Output is correct
4 Correct 265 ms 12804 KB Output is correct
5 Correct 265 ms 12696 KB Output is correct
6 Correct 255 ms 12696 KB Output is correct
7 Correct 263 ms 12748 KB Output is correct
8 Correct 261 ms 12708 KB Output is correct
9 Correct 294 ms 12784 KB Output is correct
10 Correct 268 ms 12724 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 12748 KB Output is correct
2 Correct 265 ms 12808 KB Output is correct
3 Correct 264 ms 12796 KB Output is correct
4 Correct 265 ms 12804 KB Output is correct
5 Correct 265 ms 12696 KB Output is correct
6 Correct 255 ms 12696 KB Output is correct
7 Correct 263 ms 12748 KB Output is correct
8 Correct 261 ms 12708 KB Output is correct
9 Correct 294 ms 12784 KB Output is correct
10 Correct 268 ms 12724 KB Output is correct
11 Correct 443 ms 17608 KB Output is correct
12 Correct 507 ms 17404 KB Output is correct
13 Correct 477 ms 16484 KB Output is correct
14 Correct 483 ms 16564 KB Output is correct
15 Correct 497 ms 17580 KB Output is correct
16 Correct 505 ms 16832 KB Output is correct
17 Correct 534 ms 17368 KB Output is correct
18 Correct 480 ms 19232 KB Output is correct
19 Correct 561 ms 16348 KB Output is correct
20 Correct 512 ms 17964 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 12748 KB Output is correct
2 Correct 265 ms 12808 KB Output is correct
3 Correct 264 ms 12796 KB Output is correct
4 Correct 265 ms 12804 KB Output is correct
5 Correct 265 ms 12696 KB Output is correct
6 Correct 255 ms 12696 KB Output is correct
7 Correct 263 ms 12748 KB Output is correct
8 Correct 261 ms 12708 KB Output is correct
9 Correct 294 ms 12784 KB Output is correct
10 Correct 268 ms 12724 KB Output is correct
11 Correct 443 ms 17608 KB Output is correct
12 Correct 507 ms 17404 KB Output is correct
13 Correct 477 ms 16484 KB Output is correct
14 Correct 483 ms 16564 KB Output is correct
15 Correct 497 ms 17580 KB Output is correct
16 Correct 505 ms 16832 KB Output is correct
17 Correct 534 ms 17368 KB Output is correct
18 Correct 480 ms 19232 KB Output is correct
19 Correct 561 ms 16348 KB Output is correct
20 Correct 512 ms 17964 KB Output is correct
21 Correct 509 ms 18652 KB Output is correct
22 Correct 569 ms 18760 KB Output is correct
23 Correct 598 ms 17828 KB Output is correct
24 Correct 593 ms 17596 KB Output is correct
25 Correct 584 ms 19656 KB Output is correct
26 Correct 625 ms 18124 KB Output is correct
27 Correct 613 ms 18100 KB Output is correct
28 Correct 548 ms 20652 KB Output is correct
29 Correct 581 ms 16644 KB Output is correct
30 Correct 565 ms 18796 KB Output is correct
31 Correct 675 ms 19424 KB Output is correct
32 Correct 649 ms 19488 KB Output is correct
33 Correct 619 ms 18360 KB Output is correct
34 Correct 683 ms 18440 KB Output is correct
35 Correct 610 ms 18900 KB Output is correct
36 Correct 496 ms 17440 KB Output is correct
37 Correct 566 ms 19404 KB Output is correct
38 Correct 565 ms 17488 KB Output is correct
39 Correct 550 ms 18696 KB Output is correct
40 Correct 591 ms 18432 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 12748 KB Output is correct
2 Correct 265 ms 12808 KB Output is correct
3 Correct 264 ms 12796 KB Output is correct
4 Correct 265 ms 12804 KB Output is correct
5 Correct 265 ms 12696 KB Output is correct
6 Correct 255 ms 12696 KB Output is correct
7 Correct 263 ms 12748 KB Output is correct
8 Correct 261 ms 12708 KB Output is correct
9 Correct 294 ms 12784 KB Output is correct
10 Correct 268 ms 12724 KB Output is correct
11 Correct 1010 ms 24036 KB Output is correct
12 Correct 987 ms 23344 KB Output is correct
13 Correct 1000 ms 23280 KB Output is correct
14 Correct 1014 ms 23340 KB Output is correct
15 Correct 1042 ms 23460 KB Output is correct
16 Correct 1037 ms 23300 KB Output is correct
17 Correct 1040 ms 23336 KB Output is correct
18 Correct 980 ms 23388 KB Output is correct
19 Correct 1050 ms 23220 KB Output is correct
20 Correct 1034 ms 23484 KB Output is correct
21 Correct 1037 ms 23392 KB Output is correct
22 Correct 1040 ms 23392 KB Output is correct
23 Correct 1037 ms 23372 KB Output is correct
24 Correct 1042 ms 23300 KB Output is correct
25 Correct 1075 ms 23324 KB Output is correct
26 Correct 1018 ms 23304 KB Output is correct
27 Correct 1110 ms 23212 KB Output is correct
28 Correct 1086 ms 23300 KB Output is correct
29 Correct 1046 ms 23420 KB Output is correct
30 Correct 1051 ms 23324 KB Output is correct
31 Correct 1024 ms 23248 KB Output is correct
32 Correct 1097 ms 23292 KB Output is correct
33 Correct 1052 ms 23336 KB Output is correct
34 Correct 1034 ms 23004 KB Output is correct
35 Correct 1045 ms 23328 KB Output is correct
36 Correct 1179 ms 23332 KB Output is correct
37 Correct 1186 ms 23344 KB Output is correct
38 Correct 1159 ms 23444 KB Output is correct
39 Correct 1184 ms 23464 KB Output is correct
40 Correct 1288 ms 23480 KB Output is correct

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 12748 KB Output is correct
2 Correct 265 ms 12808 KB Output is correct
3 Correct 264 ms 12796 KB Output is correct
4 Correct 265 ms 12804 KB Output is correct
5 Correct 265 ms 12696 KB Output is correct
6 Correct 255 ms 12696 KB Output is correct
7 Correct 263 ms 12748 KB Output is correct
8 Correct 261 ms 12708 KB Output is correct
9 Correct 294 ms 12784 KB Output is correct
10 Correct 268 ms 12724 KB Output is correct
11 Correct 443 ms 17608 KB Output is correct
12 Correct 507 ms 17404 KB Output is correct
13 Correct 477 ms 16484 KB Output is correct
14 Correct 483 ms 16564 KB Output is correct
15 Correct 497 ms 17580 KB Output is correct
16 Correct 505 ms 16832 KB Output is correct
17 Correct 534 ms 17368 KB Output is correct
18 Correct 480 ms 19232 KB Output is correct
19 Correct 561 ms 16348 KB Output is correct
20 Correct 512 ms 17964 KB Output is correct
21 Correct 509 ms 18652 KB Output is correct
22 Correct 569 ms 18760 KB Output is correct
23 Correct 598 ms 17828 KB Output is correct
24 Correct 593 ms 17596 KB Output is correct
25 Correct 584 ms 19656 KB Output is correct
26 Correct 625 ms 18124 KB Output is correct
27 Correct 613 ms 18100 KB Output is correct
28 Correct 548 ms 20652 KB Output is correct
29 Correct 581 ms 16644 KB Output is correct
30 Correct 565 ms 18796 KB Output is correct
31 Correct 675 ms 19424 KB Output is correct
32 Correct 649 ms 19488 KB Output is correct
33 Correct 619 ms 18360 KB Output is correct
34 Correct 683 ms 18440 KB Output is correct
35 Correct 610 ms 18900 KB Output is correct
36 Correct 496 ms 17440 KB Output is correct
37 Correct 566 ms 19404 KB Output is correct
38 Correct 565 ms 17488 KB Output is correct
39 Correct 550 ms 18696 KB Output is correct
40 Correct 591 ms 18432 KB Output is correct
41 Correct 1010 ms 24036 KB Output is correct
42 Correct 987 ms 23344 KB Output is correct
43 Correct 1000 ms 23280 KB Output is correct
44 Correct 1014 ms 23340 KB Output is correct
45 Correct 1042 ms 23460 KB Output is correct
46 Correct 1037 ms 23300 KB Output is correct
47 Correct 1040 ms 23336 KB Output is correct
48 Correct 980 ms 23388 KB Output is correct
49 Correct 1050 ms 23220 KB Output is correct
50 Correct 1034 ms 23484 KB Output is correct
51 Correct 1037 ms 23392 KB Output is correct
52 Correct 1040 ms 23392 KB Output is correct
53 Correct 1037 ms 23372 KB Output is correct
54 Correct 1042 ms 23300 KB Output is correct
55 Correct 1075 ms 23324 KB Output is correct
56 Correct 1018 ms 23304 KB Output is correct
57 Correct 1110 ms 23212 KB Output is correct
58 Correct 1086 ms 23300 KB Output is correct
59 Correct 1046 ms 23420 KB Output is correct
60 Correct 1051 ms 23324 KB Output is correct
61 Correct 1024 ms 23248 KB Output is correct
62 Correct 1097 ms 23292 KB Output is correct
63 Correct 1052 ms 23336 KB Output is correct
64 Correct 1034 ms 23004 KB Output is correct
65 Correct 1045 ms 23328 KB Output is correct
66 Correct 1179 ms 23332 KB Output is correct
67 Correct 1186 ms 23344 KB Output is correct
68 Correct 1159 ms 23444 KB Output is correct
69 Correct 1184 ms 23464 KB Output is correct
70 Correct 1288 ms 23480 KB Output is correct
71 Correct 1677 ms 42884 KB Output is correct
72 Correct 1658 ms 39096 KB Output is correct
73 Correct 1845 ms 41460 KB Output is correct
74 Execution timed out 2009 ms 41872 KB Time limit exceeded
75 Halted 0 ms 0 KB -