oj.uz

Submission #548448

# Submission time Handle Problem Language Result Execution time Memory
548448 2022-04-13T12:43:29 Z MilosMilutinovic Snake Escaping (JOI18_snake_escaping) C++14
22 / 100
 936 ms 19168 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=(1<<20)+5;
const int M=1600050;
const int Q=1000050;
int l,n,q,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();
	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);
		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));
	}
	for(int i=0;i<128;i++){
		for(int j=0;j<M;j++)dp[j]=0;
		for(int j=0;j<(1<<(l-7));j++)dp[msk[(j<<7)+i]]+=(int)(s[(j<<7)+i]-'0');
		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: In function 'void calc()':
snake_escaping.cpp:18:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |   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:51:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   51 |   while(bits.size()<l)bits.pb(0);
      |         ~~~~~~~~~~~^~
snake_escaping.cpp: In function 'void BruteForce()':
snake_escaping.cpp:33:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |   scanf("%s",qs);
      |   ~~~~~^~~~~~~~~
snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:40:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |  scanf("%i%i",&l,&q);
      |  ~~~~~^~~~~~~~~~~~~~
snake_escaping.cpp:41:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |  scanf("%s",s);
      |  ~~~~~^~~~~~~~
snake_escaping.cpp:56:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |   scanf("%s",qs);
      |   ~~~~~^~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 12876 KB Output is correct
2 Correct 267 ms 12864 KB Output is correct
3 Correct 267 ms 12748 KB Output is correct
4 Correct 265 ms 12788 KB Output is correct
5 Correct 297 ms 12740 KB Output is correct
6 Correct 268 ms 12712 KB Output is correct
7 Correct 271 ms 12748 KB Output is correct
8 Correct 270 ms 12792 KB Output is correct
9 Correct 269 ms 12824 KB Output is correct
10 Correct 265 ms 12732 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 12876 KB Output is correct
2 Correct 267 ms 12864 KB Output is correct
3 Correct 267 ms 12748 KB Output is correct
4 Correct 265 ms 12788 KB Output is correct
5 Correct 297 ms 12740 KB Output is correct
6 Correct 268 ms 12712 KB Output is correct
7 Correct 271 ms 12748 KB Output is correct
8 Correct 270 ms 12792 KB Output is correct
9 Correct 269 ms 12824 KB Output is correct
10 Correct 265 ms 12732 KB Output is correct
11 Correct 438 ms 16820 KB Output is correct
12 Correct 478 ms 16536 KB Output is correct
13 Correct 478 ms 15808 KB Output is correct
14 Correct 469 ms 15804 KB Output is correct
15 Correct 460 ms 16848 KB Output is correct
16 Correct 473 ms 15892 KB Output is correct
17 Correct 488 ms 15988 KB Output is correct
18 Correct 445 ms 17868 KB Output is correct
19 Correct 501 ms 14760 KB Output is correct
20 Correct 474 ms 16388 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 12876 KB Output is correct
2 Correct 267 ms 12864 KB Output is correct
3 Correct 267 ms 12748 KB Output is correct
4 Correct 265 ms 12788 KB Output is correct
5 Correct 297 ms 12740 KB Output is correct
6 Correct 268 ms 12712 KB Output is correct
7 Correct 271 ms 12748 KB Output is correct
8 Correct 270 ms 12792 KB Output is correct
9 Correct 269 ms 12824 KB Output is correct
10 Correct 265 ms 12732 KB Output is correct
11 Correct 438 ms 16820 KB Output is correct
12 Correct 478 ms 16536 KB Output is correct
13 Correct 478 ms 15808 KB Output is correct
14 Correct 469 ms 15804 KB Output is correct
15 Correct 460 ms 16848 KB Output is correct
16 Correct 473 ms 15892 KB Output is correct
17 Correct 488 ms 15988 KB Output is correct
18 Correct 445 ms 17868 KB Output is correct
19 Correct 501 ms 14760 KB Output is correct
20 Correct 474 ms 16388 KB Output is correct
21 Correct 447 ms 16792 KB Output is correct
22 Correct 510 ms 16968 KB Output is correct
23 Correct 527 ms 16028 KB Output is correct
24 Correct 494 ms 15944 KB Output is correct
25 Correct 502 ms 17780 KB Output is correct
26 Correct 524 ms 16288 KB Output is correct
27 Correct 530 ms 16260 KB Output is correct
28 Correct 454 ms 18764 KB Output is correct
29 Correct 487 ms 14864 KB Output is correct
30 Correct 445 ms 17052 KB Output is correct
31 Correct 499 ms 16748 KB Output is correct
32 Correct 492 ms 16728 KB Output is correct
33 Correct 470 ms 15820 KB Output is correct
34 Correct 504 ms 15820 KB Output is correct
35 Correct 524 ms 16224 KB Output is correct
36 Correct 442 ms 14796 KB Output is correct
37 Correct 496 ms 16844 KB Output is correct
38 Correct 504 ms 14816 KB Output is correct
39 Correct 499 ms 15964 KB Output is correct
40 Correct 504 ms 15832 KB Output is correct

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 12876 KB Output is correct
2 Correct 267 ms 12864 KB Output is correct
3 Correct 267 ms 12748 KB Output is correct
4 Correct 265 ms 12788 KB Output is correct
5 Correct 297 ms 12740 KB Output is correct
6 Correct 268 ms 12712 KB Output is correct
7 Correct 271 ms 12748 KB Output is correct
8 Correct 270 ms 12792 KB Output is correct
9 Correct 269 ms 12824 KB Output is correct
10 Correct 265 ms 12732 KB Output is correct
11 Incorrect 936 ms 19168 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 12876 KB Output is correct
2 Correct 267 ms 12864 KB Output is correct
3 Correct 267 ms 12748 KB Output is correct
4 Correct 265 ms 12788 KB Output is correct
5 Correct 297 ms 12740 KB Output is correct
6 Correct 268 ms 12712 KB Output is correct
7 Correct 271 ms 12748 KB Output is correct
8 Correct 270 ms 12792 KB Output is correct
9 Correct 269 ms 12824 KB Output is correct
10 Correct 265 ms 12732 KB Output is correct
11 Correct 438 ms 16820 KB Output is correct
12 Correct 478 ms 16536 KB Output is correct
13 Correct 478 ms 15808 KB Output is correct
14 Correct 469 ms 15804 KB Output is correct
15 Correct 460 ms 16848 KB Output is correct
16 Correct 473 ms 15892 KB Output is correct
17 Correct 488 ms 15988 KB Output is correct
18 Correct 445 ms 17868 KB Output is correct
19 Correct 501 ms 14760 KB Output is correct
20 Correct 474 ms 16388 KB Output is correct
21 Correct 447 ms 16792 KB Output is correct
22 Correct 510 ms 16968 KB Output is correct
23 Correct 527 ms 16028 KB Output is correct
24 Correct 494 ms 15944 KB Output is correct
25 Correct 502 ms 17780 KB Output is correct
26 Correct 524 ms 16288 KB Output is correct
27 Correct 530 ms 16260 KB Output is correct
28 Correct 454 ms 18764 KB Output is correct
29 Correct 487 ms 14864 KB Output is correct
30 Correct 445 ms 17052 KB Output is correct
31 Correct 499 ms 16748 KB Output is correct
32 Correct 492 ms 16728 KB Output is correct
33 Correct 470 ms 15820 KB Output is correct
34 Correct 504 ms 15820 KB Output is correct
35 Correct 524 ms 16224 KB Output is correct
36 Correct 442 ms 14796 KB Output is correct
37 Correct 496 ms 16844 KB Output is correct
38 Correct 504 ms 14816 KB Output is correct
39 Correct 499 ms 15964 KB Output is correct
40 Correct 504 ms 15832 KB Output is correct
41 Incorrect 936 ms 19168 KB Output isn't correct
42 Halted 0 ms 0 KB -