oj.uz

Submission #548379

# Submission time Handle Problem Language Result Execution time Memory
548379 2022-04-13T07:52:30 Z MilosMilutinovic Snake Escaping (JOI18_snake_escaping) C++14
22 / 100
 898 ms 18796 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],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<<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]-'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)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:17:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |   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:50:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   50 |   while(bits.size()<l)bits.pb(0);
      |         ~~~~~~~~~~~^~
snake_escaping.cpp: In function 'void BruteForce()':
snake_escaping.cpp:32:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |   scanf("%s",qs);
      |   ~~~~~^~~~~~~~~
snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:39:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |  scanf("%i%i",&l,&q);
      |  ~~~~~^~~~~~~~~~~~~~
snake_escaping.cpp:40:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |  scanf("%s",s);
      |  ~~~~~^~~~~~~~
snake_escaping.cpp:55:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |   scanf("%s",qs);
      |   ~~~~~^~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 267 ms 12748 KB Output is correct
2 Correct 265 ms 12856 KB Output is correct
3 Correct 265 ms 12816 KB Output is correct
4 Correct 257 ms 12780 KB Output is correct
5 Correct 264 ms 12848 KB Output is correct
6 Correct 262 ms 12804 KB Output is correct
7 Correct 262 ms 12812 KB Output is correct
8 Correct 270 ms 12828 KB Output is correct
9 Correct 264 ms 12860 KB Output is correct
10 Correct 266 ms 12972 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 267 ms 12748 KB Output is correct
2 Correct 265 ms 12856 KB Output is correct
3 Correct 265 ms 12816 KB Output is correct
4 Correct 257 ms 12780 KB Output is correct
5 Correct 264 ms 12848 KB Output is correct
6 Correct 262 ms 12804 KB Output is correct
7 Correct 262 ms 12812 KB Output is correct
8 Correct 270 ms 12828 KB Output is correct
9 Correct 264 ms 12860 KB Output is correct
10 Correct 266 ms 12972 KB Output is correct
11 Correct 440 ms 16820 KB Output is correct
12 Correct 490 ms 16492 KB Output is correct
13 Correct 484 ms 15700 KB Output is correct
14 Correct 465 ms 15948 KB Output is correct
15 Correct 482 ms 16728 KB Output is correct
16 Correct 470 ms 16068 KB Output is correct
17 Correct 476 ms 16132 KB Output is correct
18 Correct 430 ms 17740 KB Output is correct
19 Correct 473 ms 14724 KB Output is correct
20 Correct 444 ms 16500 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 267 ms 12748 KB Output is correct
2 Correct 265 ms 12856 KB Output is correct
3 Correct 265 ms 12816 KB Output is correct
4 Correct 257 ms 12780 KB Output is correct
5 Correct 264 ms 12848 KB Output is correct
6 Correct 262 ms 12804 KB Output is correct
7 Correct 262 ms 12812 KB Output is correct
8 Correct 270 ms 12828 KB Output is correct
9 Correct 264 ms 12860 KB Output is correct
10 Correct 266 ms 12972 KB Output is correct
11 Correct 440 ms 16820 KB Output is correct
12 Correct 490 ms 16492 KB Output is correct
13 Correct 484 ms 15700 KB Output is correct
14 Correct 465 ms 15948 KB Output is correct
15 Correct 482 ms 16728 KB Output is correct
16 Correct 470 ms 16068 KB Output is correct
17 Correct 476 ms 16132 KB Output is correct
18 Correct 430 ms 17740 KB Output is correct
19 Correct 473 ms 14724 KB Output is correct
20 Correct 444 ms 16500 KB Output is correct
21 Correct 464 ms 16824 KB Output is correct
22 Correct 514 ms 16960 KB Output is correct
23 Correct 506 ms 15996 KB Output is correct
24 Correct 500 ms 15884 KB Output is correct
25 Correct 487 ms 17880 KB Output is correct
26 Correct 513 ms 16320 KB Output is correct
27 Correct 526 ms 16308 KB Output is correct
28 Correct 449 ms 18768 KB Output is correct
29 Correct 495 ms 14844 KB Output is correct
30 Correct 450 ms 16904 KB Output is correct
31 Correct 507 ms 16876 KB Output is correct
32 Correct 484 ms 16816 KB Output is correct
33 Correct 469 ms 15652 KB Output is correct
34 Correct 501 ms 15792 KB Output is correct
35 Correct 536 ms 16276 KB Output is correct
36 Correct 436 ms 14912 KB Output is correct
37 Correct 491 ms 16848 KB Output is correct
38 Correct 523 ms 14804 KB Output is correct
39 Correct 496 ms 16124 KB Output is correct
40 Correct 494 ms 15804 KB Output is correct

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 267 ms 12748 KB Output is correct
2 Correct 265 ms 12856 KB Output is correct
3 Correct 265 ms 12816 KB Output is correct
4 Correct 257 ms 12780 KB Output is correct
5 Correct 264 ms 12848 KB Output is correct
6 Correct 262 ms 12804 KB Output is correct
7 Correct 262 ms 12812 KB Output is correct
8 Correct 270 ms 12828 KB Output is correct
9 Correct 264 ms 12860 KB Output is correct
10 Correct 266 ms 12972 KB Output is correct
11 Incorrect 898 ms 18796 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 267 ms 12748 KB Output is correct
2 Correct 265 ms 12856 KB Output is correct
3 Correct 265 ms 12816 KB Output is correct
4 Correct 257 ms 12780 KB Output is correct
5 Correct 264 ms 12848 KB Output is correct
6 Correct 262 ms 12804 KB Output is correct
7 Correct 262 ms 12812 KB Output is correct
8 Correct 270 ms 12828 KB Output is correct
9 Correct 264 ms 12860 KB Output is correct
10 Correct 266 ms 12972 KB Output is correct
11 Correct 440 ms 16820 KB Output is correct
12 Correct 490 ms 16492 KB Output is correct
13 Correct 484 ms 15700 KB Output is correct
14 Correct 465 ms 15948 KB Output is correct
15 Correct 482 ms 16728 KB Output is correct
16 Correct 470 ms 16068 KB Output is correct
17 Correct 476 ms 16132 KB Output is correct
18 Correct 430 ms 17740 KB Output is correct
19 Correct 473 ms 14724 KB Output is correct
20 Correct 444 ms 16500 KB Output is correct
21 Correct 464 ms 16824 KB Output is correct
22 Correct 514 ms 16960 KB Output is correct
23 Correct 506 ms 15996 KB Output is correct
24 Correct 500 ms 15884 KB Output is correct
25 Correct 487 ms 17880 KB Output is correct
26 Correct 513 ms 16320 KB Output is correct
27 Correct 526 ms 16308 KB Output is correct
28 Correct 449 ms 18768 KB Output is correct
29 Correct 495 ms 14844 KB Output is correct
30 Correct 450 ms 16904 KB Output is correct
31 Correct 507 ms 16876 KB Output is correct
32 Correct 484 ms 16816 KB Output is correct
33 Correct 469 ms 15652 KB Output is correct
34 Correct 501 ms 15792 KB Output is correct
35 Correct 536 ms 16276 KB Output is correct
36 Correct 436 ms 14912 KB Output is correct
37 Correct 491 ms 16848 KB Output is correct
38 Correct 523 ms 14804 KB Output is correct
39 Correct 496 ms 16124 KB Output is correct
40 Correct 494 ms 15804 KB Output is correct
41 Incorrect 898 ms 18796 KB Output isn't correct
42 Halted 0 ms 0 KB -