Submission #160125

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
160125	2019-10-26T05:51:38 Z	GioChkhaidze	Snake Escaping (JOI18_snake_escaping)	C++14	22 / 100	762 ms	65536 KB

snake_escaping

#include <bits/stdc++.h>
using namespace std;
int n,q,C[(1<<21)],M[20],dp[2594323],ANS[1000006],Y[1000006],vs;
string S[1000006];
main () { 
	ios::sync_with_stdio(false);
	cin>>n>>q;
	
	M[0]=1;
	for (int i=1; i<=13; i++) 
		M[i]=M[i-1]*3;
	
	if (n<=13) {	
		
		for (int i=0; i<(1<<n); i++) {
			char c;
			cin>>c;
			C[i]=c-'0';
			
			int x=0;
			for (int j=0; j<n; j++) 
				if (i&(1<<j)) x+=M[j];
			dp[x]+=C[i];
		}
		
		for (int i=0; i<M[n]; i++) {
			int x=i;
			for (int j=n-1; j>=0; j--) 
				if (x-2*M[j]>=0) x-=2*M[j],dp[i]=(dp[i-2*M[j]]+dp[i-M[j]]);	
					else
				if (x-M[j]>=0) x-=M[j];
		}
		
		for (int i=1; i<=q; i++) {
			string s;
			int x=0;
			cin>>s;	
					
			for (int j=0; j<s.size(); j++) 
				if (s[s.size()-j-1]=='?') x+=2*M[j];	
					else
				if (s[s.size()-j-1]=='1') x+=M[j];
			
			printf("%d\n",dp[x]);
		}
	}
		else {
		for (int i=0; i<(1<<n); i++) {
			char c;
			cin>>c;
			C[i]=c-'0';
		}

		int K=(n-13);
		
		bool Bo[q][(1<<7)];
		
		for (int i=1; i<=q; i++) {
			cin>>S[i];	
			
			for (int k=S[i].size()-1; k>=K; k--) {
				if (S[i][k]=='?') Y[i]+=2*M[k-S[i].size()+1];	
					else
				if (S[i][k]=='1') Y[i]+=M[k-S[i].size()+1];
			}
			
			int Bit=0;
			for (int k=0; k<K; k++) 
				if (S[i][k]=='1') Bit+=(1<<k);

			for (int j=0; j<(1<<K); j++) 
				if (j&Bit==Bit) Bo[i][j]=1;
		}
		
		int Last2[M[13]+5];
		
		for (int i=0; i<M[13]; i++) {
			int x=i;
			
			Last2[i]=-1;
			
			for (int j=12; j>=0; j--) 
				if (x>=2*M[j]) { Last2[i]=j; break; }
						else
				if (x>=M[j]) x-=M[j];
		}
		 

		for (int i=0; i<(1<<K); i++) {
			for (int j=0; j<M[13]; j++)
				dp[j]=0;
			
			for (int j=0; j<(1<<13); j++) {
				int x=0;
				for (int k=0; k<13; k++) 
					if (i&(1<<k)) x+=M[k];
				dp[x]=C[i*(1<<13)+j];
			}
			
			for (int j=0; j<M[13]; j++) {
				int x=j;
				if (Last2[j]==-1) continue;
				dp[j]=(dp[j-2*M[Last2[j]]]+dp[j-M[Last2[j]]]);	
			}
			
			for (int j=1; j<=q; j++) {
				if (!Bo[j][i]) continue;
				ANS[j]+=dp[Y[i]];
			}
		}
		
		for (int i=1; i<=q; i++) 
			printf("%d\n",ANS[i]);		
	}
}

Compilation message

snake_escaping.cpp:5:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () { 
       ^
snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:39:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int j=0; j<s.size(); j++) 
                  ~^~~~~~~~~
snake_escaping.cpp:72:14: warning: self-comparison always evaluates to true [-Wtautological-compare]
     if (j&Bit==Bit) Bo[i][j]=1;
           ~~~^~~~~
snake_escaping.cpp:72:14: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
snake_escaping.cpp:101:9: warning: unused variable 'x' [-Wunused-variable]
     int x=j;
         ^

Subtask #1
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	31 ms	31864 KB	Output is correct
2	Correct	33 ms	31964 KB	Output is correct
3	Correct	32 ms	31868 KB	Output is correct
4	Correct	34 ms	31992 KB	Output is correct
5	Correct	33 ms	31864 KB	Output is correct
6	Correct	40 ms	31864 KB	Output is correct
7	Correct	34 ms	32004 KB	Output is correct
8	Correct	35 ms	31992 KB	Output is correct
9	Correct	34 ms	31864 KB	Output is correct
10	Correct	34 ms	31864 KB	Output is correct

Subtask #2
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	31 ms	31864 KB	Output is correct
2	Correct	33 ms	31964 KB	Output is correct
3	Correct	32 ms	31868 KB	Output is correct
4	Correct	34 ms	31992 KB	Output is correct
5	Correct	33 ms	31864 KB	Output is correct
6	Correct	40 ms	31864 KB	Output is correct
7	Correct	34 ms	32004 KB	Output is correct
8	Correct	35 ms	31992 KB	Output is correct
9	Correct	34 ms	31864 KB	Output is correct
10	Correct	34 ms	31864 KB	Output is correct
11	Correct	288 ms	46792 KB	Output is correct
12	Correct	306 ms	46504 KB	Output is correct
13	Correct	317 ms	45560 KB	Output is correct
14	Correct	321 ms	45892 KB	Output is correct
15	Correct	314 ms	46712 KB	Output is correct
16	Correct	343 ms	45952 KB	Output is correct
17	Correct	531 ms	45944 KB	Output is correct
18	Correct	237 ms	47736 KB	Output is correct
19	Correct	286 ms	44728 KB	Output is correct
20	Correct	309 ms	46456 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	31 ms	31864 KB	Output is correct
2	Correct	33 ms	31964 KB	Output is correct
3	Correct	32 ms	31868 KB	Output is correct
4	Correct	34 ms	31992 KB	Output is correct
5	Correct	33 ms	31864 KB	Output is correct
6	Correct	40 ms	31864 KB	Output is correct
7	Correct	34 ms	32004 KB	Output is correct
8	Correct	35 ms	31992 KB	Output is correct
9	Correct	34 ms	31864 KB	Output is correct
10	Correct	34 ms	31864 KB	Output is correct
11	Correct	288 ms	46792 KB	Output is correct
12	Correct	306 ms	46504 KB	Output is correct
13	Correct	317 ms	45560 KB	Output is correct
14	Correct	321 ms	45892 KB	Output is correct
15	Correct	314 ms	46712 KB	Output is correct
16	Correct	343 ms	45952 KB	Output is correct
17	Correct	531 ms	45944 KB	Output is correct
18	Correct	237 ms	47736 KB	Output is correct
19	Correct	286 ms	44728 KB	Output is correct
20	Correct	309 ms	46456 KB	Output is correct
21	Correct	380 ms	55792 KB	Output is correct
22	Correct	408 ms	56048 KB	Output is correct
23	Correct	466 ms	54908 KB	Output is correct
24	Correct	468 ms	54896 KB	Output is correct
25	Correct	434 ms	56772 KB	Output is correct
26	Correct	486 ms	55288 KB	Output is correct
27	Correct	484 ms	55160 KB	Output is correct
28	Correct	311 ms	57840 KB	Output is correct
29	Correct	376 ms	53752 KB	Output is correct
30	Correct	391 ms	55800 KB	Output is correct
31	Correct	499 ms	55748 KB	Output is correct
32	Correct	473 ms	55796 KB	Output is correct
33	Correct	400 ms	54520 KB	Output is correct
34	Correct	474 ms	54776 KB	Output is correct
35	Correct	508 ms	55176 KB	Output is correct
36	Correct	305 ms	53632 KB	Output is correct
37	Correct	383 ms	55916 KB	Output is correct
38	Correct	383 ms	53748 KB	Output is correct
39	Correct	471 ms	55032 KB	Output is correct
40	Correct	458 ms	54696 KB	Output is correct

Subtask #4
0 / 53.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	31 ms	31864 KB	Output is correct
2	Correct	33 ms	31964 KB	Output is correct
3	Correct	32 ms	31868 KB	Output is correct
4	Correct	34 ms	31992 KB	Output is correct
5	Correct	33 ms	31864 KB	Output is correct
6	Correct	40 ms	31864 KB	Output is correct
7	Correct	34 ms	32004 KB	Output is correct
8	Correct	35 ms	31992 KB	Output is correct
9	Correct	34 ms	31864 KB	Output is correct
10	Correct	34 ms	31864 KB	Output is correct
11	Runtime error	762 ms	65536 KB	Execution killed with signal 7 (could be triggered by violating memory limits)
12	Halted	0 ms	0 KB	-

Subtask #5
0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	31 ms	31864 KB	Output is correct
2	Correct	33 ms	31964 KB	Output is correct
3	Correct	32 ms	31868 KB	Output is correct
4	Correct	34 ms	31992 KB	Output is correct
5	Correct	33 ms	31864 KB	Output is correct
6	Correct	40 ms	31864 KB	Output is correct
7	Correct	34 ms	32004 KB	Output is correct
8	Correct	35 ms	31992 KB	Output is correct
9	Correct	34 ms	31864 KB	Output is correct
10	Correct	34 ms	31864 KB	Output is correct
11	Correct	288 ms	46792 KB	Output is correct
12	Correct	306 ms	46504 KB	Output is correct
13	Correct	317 ms	45560 KB	Output is correct
14	Correct	321 ms	45892 KB	Output is correct
15	Correct	314 ms	46712 KB	Output is correct
16	Correct	343 ms	45952 KB	Output is correct
17	Correct	531 ms	45944 KB	Output is correct
18	Correct	237 ms	47736 KB	Output is correct
19	Correct	286 ms	44728 KB	Output is correct
20	Correct	309 ms	46456 KB	Output is correct
21	Correct	380 ms	55792 KB	Output is correct
22	Correct	408 ms	56048 KB	Output is correct
23	Correct	466 ms	54908 KB	Output is correct
24	Correct	468 ms	54896 KB	Output is correct
25	Correct	434 ms	56772 KB	Output is correct
26	Correct	486 ms	55288 KB	Output is correct
27	Correct	484 ms	55160 KB	Output is correct
28	Correct	311 ms	57840 KB	Output is correct
29	Correct	376 ms	53752 KB	Output is correct
30	Correct	391 ms	55800 KB	Output is correct
31	Correct	499 ms	55748 KB	Output is correct
32	Correct	473 ms	55796 KB	Output is correct
33	Correct	400 ms	54520 KB	Output is correct
34	Correct	474 ms	54776 KB	Output is correct
35	Correct	508 ms	55176 KB	Output is correct
36	Correct	305 ms	53632 KB	Output is correct
37	Correct	383 ms	55916 KB	Output is correct
38	Correct	383 ms	53748 KB	Output is correct
39	Correct	471 ms	55032 KB	Output is correct
40	Correct	458 ms	54696 KB	Output is correct
41	Runtime error	762 ms	65536 KB	Execution killed with signal 7 (could be triggered by violating memory limits)
42	Halted	0 ms	0 KB	-

Submission #160125

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