Submission #66943

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
66943	2018-08-12T20:09:19 Z	hamzqq9	Snake Escaping (JOI18_snake_escaping)	C++14	22 / 100	1602 ms	29492 KB

snake_escaping

#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define ppb pop_back
#define umax(x,y) x=max(x,y)
#define umin(x,y) x=min(x,y)
#define ll long long
#define ii pair<int,int>
#define iii pair<int,ii>
#define sz(x) ((int) x.size())
#define orta ((bas+son)>>1)
#define all(x) x.begin(),x.end()
#define dbgs(x) cerr<<(#x)<<" --> "<<(x)<<" "
#define dbg(x) cerr<<(#x)<<" --> "<<(x)<<endl;getchar()
#define pw(x) (1<<(x))
#define inf 100000000000000
#define MOD 1000000007
#define N 3005
#define MAX 10000006
#define LOG 22
#define L 7
#define R 13
using namespace std;
 
int n,q,l;
int cnt[1594325],ans[pw(20)+5];
int po3[20],po2[25],pos[1594325];
char val[pw(20)+5],s[pw(20)+5];
bool oops[1594325],inc[2188][129];
int Right[pw(20)+5];
short Left[pw(20)+5]; 

void do_dp(int value) {
 
	for(int i=0;i<1594323;i++) {
 
		if(oops[i]) cnt[i]=val[value*po2[R]+pos[i]];
		else cnt[i]=cnt[i-po3[pos[i]]]+cnt[i-2*po3[pos[i]]];
 
	}
 
}

void pre_cal() {

	oops[0]=oops[1]=true;
	pos[1]=1;

	for(int i=3;i<1594323;i++) {
 
 		if(i%3==2) pos[i]=0;
 		else {

 			int val=i/3;

 			if(oops[val]) {

 				oops[i]=true;
 				pos[i]=pos[val]*2+i%3;

 			}
 			else {

 				pos[i]=pos[val]+1;

 			}

 		}
 
	}

	for(int i=0;i<2187;i++) {

		if(i<3) {

			for(int j=0;j<128;j++) {

				if(i==2 || j%3==i) inc[i][j]=true;				

			}

			continue ;

		}

		for(int j=0;j<128;j++) {

			if(i%3==2 || i%3==j%2) inc[i][j]=inc[i/3][j/2]; 

		}

	}
 
}
 
int get_value(int bas,int son) {
 
	int res=0;
 
	for(int i=bas;i<=son;i++) {
 
		res=res*3+(s[i]=='?'?2:(s[i]-'0'));
 
	}
 
	return res;
 
}
 
int main() {
 
	//freopen("input.txt","r",stdin);
 
	po3[0]=po2[0]=1;
 
 	for(int i=1;i<=15;i++) po3[i]=po3[i-1]*3;

 	for(int i=1;i<=20;i++) po2[i]=po2[i-1]*2;
 
	scanf("%d %d",&l,&q);
 
	n=po2[l];
 
	scanf("%s",s);
 
	for(int i=0;i<n;i++) val[i]=s[i]-'0';
 
	for(int i=1;i<=q;i++) {
 
		scanf("%s",s+20-l);
 
		for(int i=0;i<20-l;i++) s[i]='0';
 
		Right[i]=get_value(L,19);
		Left[i]=get_value(0,L-1);
 
	}
 
	pre_cal();
 
	for(int i=0;i<po2[L];i++) {
 
		do_dp(i);
 
		for(int j=1;j<=q;j++) {

			if(inc[Left[j]][i]) {

				ans[j]+=cnt[Right[j]];

			}

		}
 
	}
 
	for(int i=1;i<=q;i++) printf("%d\n",ans[i]);
 
}

Compilation message

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:121:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&l,&q);
  ~~~~~^~~~~~~~~~~~~~~
snake_escaping.cpp:125:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s",s);
  ~~~~~^~~~~~~~
snake_escaping.cpp:131:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s",s+20-l);
   ~~~~~^~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	507 ms	13436 KB	Output is correct
2	Correct	480 ms	13532 KB	Output is correct
3	Correct	513 ms	13624 KB	Output is correct
4	Correct	455 ms	13624 KB	Output is correct
5	Correct	497 ms	13624 KB	Output is correct
6	Correct	476 ms	13624 KB	Output is correct
7	Correct	460 ms	13692 KB	Output is correct
8	Correct	481 ms	13692 KB	Output is correct
9	Correct	483 ms	13692 KB	Output is correct
10	Correct	499 ms	13720 KB	Output is correct

Subtask #2
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	507 ms	13436 KB	Output is correct
2	Correct	480 ms	13532 KB	Output is correct
3	Correct	513 ms	13624 KB	Output is correct
4	Correct	455 ms	13624 KB	Output is correct
5	Correct	497 ms	13624 KB	Output is correct
6	Correct	476 ms	13624 KB	Output is correct
7	Correct	460 ms	13692 KB	Output is correct
8	Correct	481 ms	13692 KB	Output is correct
9	Correct	483 ms	13692 KB	Output is correct
10	Correct	499 ms	13720 KB	Output is correct
11	Correct	968 ms	27424 KB	Output is correct
12	Correct	1002 ms	27424 KB	Output is correct
13	Correct	964 ms	27424 KB	Output is correct
14	Correct	979 ms	27424 KB	Output is correct
15	Correct	1028 ms	27452 KB	Output is correct
16	Correct	1030 ms	27452 KB	Output is correct
17	Correct	1147 ms	27452 KB	Output is correct
18	Correct	1006 ms	28516 KB	Output is correct
19	Correct	1032 ms	28516 KB	Output is correct
20	Correct	1020 ms	28516 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	507 ms	13436 KB	Output is correct
2	Correct	480 ms	13532 KB	Output is correct
3	Correct	513 ms	13624 KB	Output is correct
4	Correct	455 ms	13624 KB	Output is correct
5	Correct	497 ms	13624 KB	Output is correct
6	Correct	476 ms	13624 KB	Output is correct
7	Correct	460 ms	13692 KB	Output is correct
8	Correct	481 ms	13692 KB	Output is correct
9	Correct	483 ms	13692 KB	Output is correct
10	Correct	499 ms	13720 KB	Output is correct
11	Correct	968 ms	27424 KB	Output is correct
12	Correct	1002 ms	27424 KB	Output is correct
13	Correct	964 ms	27424 KB	Output is correct
14	Correct	979 ms	27424 KB	Output is correct
15	Correct	1028 ms	27452 KB	Output is correct
16	Correct	1030 ms	27452 KB	Output is correct
17	Correct	1147 ms	27452 KB	Output is correct
18	Correct	1006 ms	28516 KB	Output is correct
19	Correct	1032 ms	28516 KB	Output is correct
20	Correct	1020 ms	28516 KB	Output is correct
21	Correct	1081 ms	28516 KB	Output is correct
22	Correct	1308 ms	28516 KB	Output is correct
23	Correct	1346 ms	28516 KB	Output is correct
24	Correct	1153 ms	28516 KB	Output is correct
25	Correct	1179 ms	28516 KB	Output is correct
26	Correct	1185 ms	28516 KB	Output is correct
27	Correct	1209 ms	28516 KB	Output is correct
28	Correct	898 ms	29492 KB	Output is correct
29	Correct	951 ms	29492 KB	Output is correct
30	Correct	1287 ms	29492 KB	Output is correct
31	Correct	1258 ms	29492 KB	Output is correct
32	Correct	1375 ms	29492 KB	Output is correct
33	Correct	1148 ms	29492 KB	Output is correct
34	Correct	1251 ms	29492 KB	Output is correct
35	Correct	1602 ms	29492 KB	Output is correct
36	Correct	1004 ms	29492 KB	Output is correct
37	Correct	1201 ms	29492 KB	Output is correct
38	Correct	931 ms	29492 KB	Output is correct
39	Correct	1236 ms	29492 KB	Output is correct
40	Correct	1188 ms	29492 KB	Output is correct

Subtask #4
0 / 53.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	507 ms	13436 KB	Output is correct
2	Correct	480 ms	13532 KB	Output is correct
3	Correct	513 ms	13624 KB	Output is correct
4	Correct	455 ms	13624 KB	Output is correct
5	Correct	497 ms	13624 KB	Output is correct
6	Correct	476 ms	13624 KB	Output is correct
7	Correct	460 ms	13692 KB	Output is correct
8	Correct	481 ms	13692 KB	Output is correct
9	Correct	483 ms	13692 KB	Output is correct
10	Correct	499 ms	13720 KB	Output is correct
11	Correct	544 ms	29492 KB	Output is correct
12	Incorrect	567 ms	29492 KB	Output isn't correct
13	Halted	0 ms	0 KB	-

Subtask #5
0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	507 ms	13436 KB	Output is correct
2	Correct	480 ms	13532 KB	Output is correct
3	Correct	513 ms	13624 KB	Output is correct
4	Correct	455 ms	13624 KB	Output is correct
5	Correct	497 ms	13624 KB	Output is correct
6	Correct	476 ms	13624 KB	Output is correct
7	Correct	460 ms	13692 KB	Output is correct
8	Correct	481 ms	13692 KB	Output is correct
9	Correct	483 ms	13692 KB	Output is correct
10	Correct	499 ms	13720 KB	Output is correct
11	Correct	968 ms	27424 KB	Output is correct
12	Correct	1002 ms	27424 KB	Output is correct
13	Correct	964 ms	27424 KB	Output is correct
14	Correct	979 ms	27424 KB	Output is correct
15	Correct	1028 ms	27452 KB	Output is correct
16	Correct	1030 ms	27452 KB	Output is correct
17	Correct	1147 ms	27452 KB	Output is correct
18	Correct	1006 ms	28516 KB	Output is correct
19	Correct	1032 ms	28516 KB	Output is correct
20	Correct	1020 ms	28516 KB	Output is correct
21	Correct	1081 ms	28516 KB	Output is correct
22	Correct	1308 ms	28516 KB	Output is correct
23	Correct	1346 ms	28516 KB	Output is correct
24	Correct	1153 ms	28516 KB	Output is correct
25	Correct	1179 ms	28516 KB	Output is correct
26	Correct	1185 ms	28516 KB	Output is correct
27	Correct	1209 ms	28516 KB	Output is correct
28	Correct	898 ms	29492 KB	Output is correct
29	Correct	951 ms	29492 KB	Output is correct
30	Correct	1287 ms	29492 KB	Output is correct
31	Correct	1258 ms	29492 KB	Output is correct
32	Correct	1375 ms	29492 KB	Output is correct
33	Correct	1148 ms	29492 KB	Output is correct
34	Correct	1251 ms	29492 KB	Output is correct
35	Correct	1602 ms	29492 KB	Output is correct
36	Correct	1004 ms	29492 KB	Output is correct
37	Correct	1201 ms	29492 KB	Output is correct
38	Correct	931 ms	29492 KB	Output is correct
39	Correct	1236 ms	29492 KB	Output is correct
40	Correct	1188 ms	29492 KB	Output is correct
41	Correct	544 ms	29492 KB	Output is correct
42	Incorrect	567 ms	29492 KB	Output isn't correct
43	Halted	0 ms	0 KB	-

Submission #66943

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