답안 #548273

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
548273	2022-04-12T20:45:02 Z	MilosMilutinovic	Snake Escaping (JOI18_snake_escaping)	C++14	22 / 100	670 ms	32668 KB

snake_escaping

#include <bits/stdc++.h>
using namespace std;
const int N=(1<<20)+5;
const int M=1600050;
int l,n,q,lst[M],pw[20],ans[N],dp[M];
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;
	}
	return 0;
}

Compilation message

snake_escaping.cpp: In function 'void calc()':
snake_escaping.cpp:15:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |   for(int j=0;j<bits.size();j++)if(bits[j]==2)lst[i]=j;
      |               ~^~~~~~~~~~~~
snake_escaping.cpp: In function 'void BruteForce()':
snake_escaping.cpp:30:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |   scanf("%s",qs);
      |   ~~~~~^~~~~~~~~
snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:37:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |  scanf("%i%i",&l,&q);
      |  ~~~~~^~~~~~~~~~~~~~
snake_escaping.cpp:38:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |  scanf("%s",s);
      |  ~~~~~^~~~~~~~

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	271 ms	12780 KB	Output is correct
2	Correct	315 ms	12812 KB	Output is correct
3	Correct	287 ms	12860 KB	Output is correct
4	Correct	292 ms	12708 KB	Output is correct
5	Correct	308 ms	12768 KB	Output is correct
6	Correct	286 ms	12780 KB	Output is correct
7	Correct	308 ms	12772 KB	Output is correct
8	Correct	291 ms	12756 KB	Output is correct
9	Correct	292 ms	12844 KB	Output is correct
10	Correct	292 ms	12800 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	271 ms	12780 KB	Output is correct
2	Correct	315 ms	12812 KB	Output is correct
3	Correct	287 ms	12860 KB	Output is correct
4	Correct	292 ms	12708 KB	Output is correct
5	Correct	308 ms	12768 KB	Output is correct
6	Correct	286 ms	12780 KB	Output is correct
7	Correct	308 ms	12772 KB	Output is correct
8	Correct	291 ms	12756 KB	Output is correct
9	Correct	292 ms	12844 KB	Output is correct
10	Correct	292 ms	12800 KB	Output is correct
11	Correct	502 ms	27520 KB	Output is correct
12	Correct	533 ms	27244 KB	Output is correct
13	Correct	536 ms	26408 KB	Output is correct
14	Correct	521 ms	26536 KB	Output is correct
15	Correct	481 ms	27548 KB	Output is correct
16	Correct	520 ms	26756 KB	Output is correct
17	Correct	548 ms	26664 KB	Output is correct
18	Correct	529 ms	28496 KB	Output is correct
19	Correct	548 ms	25560 KB	Output is correct
20	Correct	500 ms	27196 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	271 ms	12780 KB	Output is correct
2	Correct	315 ms	12812 KB	Output is correct
3	Correct	287 ms	12860 KB	Output is correct
4	Correct	292 ms	12708 KB	Output is correct
5	Correct	308 ms	12768 KB	Output is correct
6	Correct	286 ms	12780 KB	Output is correct
7	Correct	308 ms	12772 KB	Output is correct
8	Correct	291 ms	12756 KB	Output is correct
9	Correct	292 ms	12844 KB	Output is correct
10	Correct	292 ms	12800 KB	Output is correct
11	Correct	502 ms	27520 KB	Output is correct
12	Correct	533 ms	27244 KB	Output is correct
13	Correct	536 ms	26408 KB	Output is correct
14	Correct	521 ms	26536 KB	Output is correct
15	Correct	481 ms	27548 KB	Output is correct
16	Correct	520 ms	26756 KB	Output is correct
17	Correct	548 ms	26664 KB	Output is correct
18	Correct	529 ms	28496 KB	Output is correct
19	Correct	548 ms	25560 KB	Output is correct
20	Correct	500 ms	27196 KB	Output is correct
21	Correct	495 ms	30524 KB	Output is correct
22	Correct	570 ms	30768 KB	Output is correct
23	Correct	563 ms	29644 KB	Output is correct
24	Correct	552 ms	29644 KB	Output is correct
25	Correct	559 ms	31564 KB	Output is correct
26	Correct	647 ms	30020 KB	Output is correct
27	Correct	630 ms	30128 KB	Output is correct
28	Correct	490 ms	32668 KB	Output is correct
29	Correct	580 ms	28448 KB	Output is correct
30	Correct	554 ms	30680 KB	Output is correct
31	Correct	604 ms	30564 KB	Output is correct
32	Correct	648 ms	30540 KB	Output is correct
33	Correct	570 ms	29396 KB	Output is correct
34	Correct	670 ms	29468 KB	Output is correct
35	Correct	628 ms	29960 KB	Output is correct
36	Correct	520 ms	28428 KB	Output is correct
37	Correct	571 ms	30480 KB	Output is correct
38	Correct	544 ms	28492 KB	Output is correct
39	Correct	586 ms	29636 KB	Output is correct
40	Correct	575 ms	29580 KB	Output is correct

Subtask #4
0 / 53.0

#	결과	실행 시간	메모리	Grader output
1	Correct	271 ms	12780 KB	Output is correct
2	Correct	315 ms	12812 KB	Output is correct
3	Correct	287 ms	12860 KB	Output is correct
4	Correct	292 ms	12708 KB	Output is correct
5	Correct	308 ms	12768 KB	Output is correct
6	Correct	286 ms	12780 KB	Output is correct
7	Correct	308 ms	12772 KB	Output is correct
8	Correct	291 ms	12756 KB	Output is correct
9	Correct	292 ms	12844 KB	Output is correct
10	Correct	292 ms	12800 KB	Output is correct
11	Incorrect	280 ms	8780 KB	Output isn't correct
12	Halted	0 ms	0 KB	-

Subtask #5
0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	271 ms	12780 KB	Output is correct
2	Correct	315 ms	12812 KB	Output is correct
3	Correct	287 ms	12860 KB	Output is correct
4	Correct	292 ms	12708 KB	Output is correct
5	Correct	308 ms	12768 KB	Output is correct
6	Correct	286 ms	12780 KB	Output is correct
7	Correct	308 ms	12772 KB	Output is correct
8	Correct	291 ms	12756 KB	Output is correct
9	Correct	292 ms	12844 KB	Output is correct
10	Correct	292 ms	12800 KB	Output is correct
11	Correct	502 ms	27520 KB	Output is correct
12	Correct	533 ms	27244 KB	Output is correct
13	Correct	536 ms	26408 KB	Output is correct
14	Correct	521 ms	26536 KB	Output is correct
15	Correct	481 ms	27548 KB	Output is correct
16	Correct	520 ms	26756 KB	Output is correct
17	Correct	548 ms	26664 KB	Output is correct
18	Correct	529 ms	28496 KB	Output is correct
19	Correct	548 ms	25560 KB	Output is correct
20	Correct	500 ms	27196 KB	Output is correct
21	Correct	495 ms	30524 KB	Output is correct
22	Correct	570 ms	30768 KB	Output is correct
23	Correct	563 ms	29644 KB	Output is correct
24	Correct	552 ms	29644 KB	Output is correct
25	Correct	559 ms	31564 KB	Output is correct
26	Correct	647 ms	30020 KB	Output is correct
27	Correct	630 ms	30128 KB	Output is correct
28	Correct	490 ms	32668 KB	Output is correct
29	Correct	580 ms	28448 KB	Output is correct
30	Correct	554 ms	30680 KB	Output is correct
31	Correct	604 ms	30564 KB	Output is correct
32	Correct	648 ms	30540 KB	Output is correct
33	Correct	570 ms	29396 KB	Output is correct
34	Correct	670 ms	29468 KB	Output is correct
35	Correct	628 ms	29960 KB	Output is correct
36	Correct	520 ms	28428 KB	Output is correct
37	Correct	571 ms	30480 KB	Output is correct
38	Correct	544 ms	28492 KB	Output is correct
39	Correct	586 ms	29636 KB	Output is correct
40	Correct	575 ms	29580 KB	Output is correct
41	Incorrect	280 ms	8780 KB	Output isn't correct
42	Halted	0 ms	0 KB	-

답안 #548273

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 7.0 / 7.0

Subtask #3 10.0 / 10.0

Subtask #4 0 / 53.0

Subtask #5 0 / 25.0

Subtask #1
5.0 / 5.0

Subtask #2
7.0 / 7.0

Subtask #3
10.0 / 10.0

Subtask #4
0 / 53.0

Subtask #5
0 / 25.0