Submission #160126

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
160126	2019-10-26T05:53:36 Z	GioChkhaidze	Snake Escaping (JOI18_snake_escaping)	C++14	22 / 100	503 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<<4)+2];
		
		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[j]];
			}
		}
		
		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	32 ms	31992 KB	Output is correct
2	Correct	31 ms	31864 KB	Output is correct
3	Correct	31 ms	31864 KB	Output is correct
4	Correct	31 ms	31992 KB	Output is correct
5	Correct	31 ms	31864 KB	Output is correct
6	Correct	31 ms	31864 KB	Output is correct
7	Correct	32 ms	32120 KB	Output is correct
8	Correct	31 ms	31992 KB	Output is correct
9	Correct	31 ms	31992 KB	Output is correct
10	Correct	30 ms	31864 KB	Output is correct

Subtask #2
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	32 ms	31992 KB	Output is correct
2	Correct	31 ms	31864 KB	Output is correct
3	Correct	31 ms	31864 KB	Output is correct
4	Correct	31 ms	31992 KB	Output is correct
5	Correct	31 ms	31864 KB	Output is correct
6	Correct	31 ms	31864 KB	Output is correct
7	Correct	32 ms	32120 KB	Output is correct
8	Correct	31 ms	31992 KB	Output is correct
9	Correct	31 ms	31992 KB	Output is correct
10	Correct	30 ms	31864 KB	Output is correct
11	Correct	286 ms	36100 KB	Output is correct
12	Correct	303 ms	35592 KB	Output is correct
13	Correct	316 ms	34936 KB	Output is correct
14	Correct	322 ms	34964 KB	Output is correct
15	Correct	313 ms	36132 KB	Output is correct
16	Correct	330 ms	35192 KB	Output is correct
17	Correct	331 ms	35064 KB	Output is correct
18	Correct	237 ms	36984 KB	Output is correct
19	Correct	292 ms	33996 KB	Output is correct
20	Correct	301 ms	35688 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	32 ms	31992 KB	Output is correct
2	Correct	31 ms	31864 KB	Output is correct
3	Correct	31 ms	31864 KB	Output is correct
4	Correct	31 ms	31992 KB	Output is correct
5	Correct	31 ms	31864 KB	Output is correct
6	Correct	31 ms	31864 KB	Output is correct
7	Correct	32 ms	32120 KB	Output is correct
8	Correct	31 ms	31992 KB	Output is correct
9	Correct	31 ms	31992 KB	Output is correct
10	Correct	30 ms	31864 KB	Output is correct
11	Correct	286 ms	36100 KB	Output is correct
12	Correct	303 ms	35592 KB	Output is correct
13	Correct	316 ms	34936 KB	Output is correct
14	Correct	322 ms	34964 KB	Output is correct
15	Correct	313 ms	36132 KB	Output is correct
16	Correct	330 ms	35192 KB	Output is correct
17	Correct	331 ms	35064 KB	Output is correct
18	Correct	237 ms	36984 KB	Output is correct
19	Correct	292 ms	33996 KB	Output is correct
20	Correct	301 ms	35688 KB	Output is correct
21	Correct	383 ms	41940 KB	Output is correct
22	Correct	393 ms	42260 KB	Output is correct
23	Correct	468 ms	41208 KB	Output is correct
24	Correct	452 ms	40952 KB	Output is correct
25	Correct	483 ms	43000 KB	Output is correct
26	Correct	480 ms	41580 KB	Output is correct
27	Correct	503 ms	41592 KB	Output is correct
28	Correct	299 ms	44024 KB	Output is correct
29	Correct	368 ms	40056 KB	Output is correct
30	Correct	394 ms	42184 KB	Output is correct
31	Correct	454 ms	41976 KB	Output is correct
32	Correct	455 ms	41976 KB	Output is correct
33	Correct	396 ms	40952 KB	Output is correct
34	Correct	467 ms	41080 KB	Output is correct
35	Correct	492 ms	41424 KB	Output is correct
36	Correct	291 ms	39960 KB	Output is correct
37	Correct	375 ms	41976 KB	Output is correct
38	Correct	393 ms	40056 KB	Output is correct
39	Correct	456 ms	41268 KB	Output is correct
40	Correct	442 ms	40956 KB	Output is correct

Subtask #4
0 / 53.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	32 ms	31992 KB	Output is correct
2	Correct	31 ms	31864 KB	Output is correct
3	Correct	31 ms	31864 KB	Output is correct
4	Correct	31 ms	31992 KB	Output is correct
5	Correct	31 ms	31864 KB	Output is correct
6	Correct	31 ms	31864 KB	Output is correct
7	Correct	32 ms	32120 KB	Output is correct
8	Correct	31 ms	31992 KB	Output is correct
9	Correct	31 ms	31992 KB	Output is correct
10	Correct	30 ms	31864 KB	Output is correct
11	Runtime error	131 ms	65536 KB	Execution killed with signal 11 (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	32 ms	31992 KB	Output is correct
2	Correct	31 ms	31864 KB	Output is correct
3	Correct	31 ms	31864 KB	Output is correct
4	Correct	31 ms	31992 KB	Output is correct
5	Correct	31 ms	31864 KB	Output is correct
6	Correct	31 ms	31864 KB	Output is correct
7	Correct	32 ms	32120 KB	Output is correct
8	Correct	31 ms	31992 KB	Output is correct
9	Correct	31 ms	31992 KB	Output is correct
10	Correct	30 ms	31864 KB	Output is correct
11	Correct	286 ms	36100 KB	Output is correct
12	Correct	303 ms	35592 KB	Output is correct
13	Correct	316 ms	34936 KB	Output is correct
14	Correct	322 ms	34964 KB	Output is correct
15	Correct	313 ms	36132 KB	Output is correct
16	Correct	330 ms	35192 KB	Output is correct
17	Correct	331 ms	35064 KB	Output is correct
18	Correct	237 ms	36984 KB	Output is correct
19	Correct	292 ms	33996 KB	Output is correct
20	Correct	301 ms	35688 KB	Output is correct
21	Correct	383 ms	41940 KB	Output is correct
22	Correct	393 ms	42260 KB	Output is correct
23	Correct	468 ms	41208 KB	Output is correct
24	Correct	452 ms	40952 KB	Output is correct
25	Correct	483 ms	43000 KB	Output is correct
26	Correct	480 ms	41580 KB	Output is correct
27	Correct	503 ms	41592 KB	Output is correct
28	Correct	299 ms	44024 KB	Output is correct
29	Correct	368 ms	40056 KB	Output is correct
30	Correct	394 ms	42184 KB	Output is correct
31	Correct	454 ms	41976 KB	Output is correct
32	Correct	455 ms	41976 KB	Output is correct
33	Correct	396 ms	40952 KB	Output is correct
34	Correct	467 ms	41080 KB	Output is correct
35	Correct	492 ms	41424 KB	Output is correct
36	Correct	291 ms	39960 KB	Output is correct
37	Correct	375 ms	41976 KB	Output is correct
38	Correct	393 ms	40056 KB	Output is correct
39	Correct	456 ms	41268 KB	Output is correct
40	Correct	442 ms	40956 KB	Output is correct
41	Runtime error	131 ms	65536 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
42	Halted	0 ms	0 KB	-

Submission #160126

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