Submission #159806

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
159806	2019-10-24T20:32:06 Z	GioChkhaidze	Snake Escaping (JOI18_snake_escaping)	C++14	22 / 100	2000 ms	57768 KB

snake_escaping

#include <bits/stdc++.h>
using namespace std;
int n,q,C[(1<<21)],M[20],dp[2594323],ANS[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';
		}
		
		for (int i=1; i<=q; i++) 
			cin>>S[i];	
	
		int K=(n-13);
		
		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;
				for (int k=12; k>=0; k--) 
					if (x-2*M[k]>=0) x-=2*M[k],dp[j]=(dp[j-2*M[k]]+dp[j-M[k]]);	
						else
					if (x-M[k]>=0) x-=M[k];
			}
			
			for (int j=1; j<=q; j++) {
				int ko=0;
				for (int k=0; k<K; k++) {
					if (
						((S[j][k]-'0')==1 && (1<<k)&i) ||
						((S[j][k]-'0')==0 && !((1<<k)&i)) ||
						S[j][k]=='?'
													  ) continue;
					ko=1;
				}
				
				if (ko) continue;
				
				int x=0;
				
				for (int k=S[j].size()-1; k>=K; k--) {
					if (S[j][k]=='?') x+=2*M[k-S[j].size()+1];	
						else
					if (S[j][k]=='1') x+=M[k-S[j].size()+1];
				}
				
				ANS[j]+=dp[x];
			}
		}
		
		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++) 
                  ~^~~~~~~~~

Subtask #1
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	31 ms	31992 KB	Output is correct
2	Correct	30 ms	31992 KB	Output is correct
3	Correct	30 ms	31944 KB	Output is correct
4	Correct	30 ms	31996 KB	Output is correct
5	Correct	31 ms	31992 KB	Output is correct
6	Correct	30 ms	31916 KB	Output is correct
7	Correct	30 ms	31992 KB	Output is correct
8	Correct	47 ms	31984 KB	Output is correct
9	Correct	70 ms	31968 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	31 ms	31992 KB	Output is correct
2	Correct	30 ms	31992 KB	Output is correct
3	Correct	30 ms	31944 KB	Output is correct
4	Correct	30 ms	31996 KB	Output is correct
5	Correct	31 ms	31992 KB	Output is correct
6	Correct	30 ms	31916 KB	Output is correct
7	Correct	30 ms	31992 KB	Output is correct
8	Correct	47 ms	31984 KB	Output is correct
9	Correct	70 ms	31968 KB	Output is correct
10	Correct	30 ms	31864 KB	Output is correct
11	Correct	286 ms	46696 KB	Output is correct
12	Correct	298 ms	46476 KB	Output is correct
13	Correct	304 ms	45652 KB	Output is correct
14	Correct	309 ms	45748 KB	Output is correct
15	Correct	332 ms	46836 KB	Output is correct
16	Correct	320 ms	45816 KB	Output is correct
17	Correct	325 ms	45916 KB	Output is correct
18	Correct	245 ms	47808 KB	Output is correct
19	Correct	277 ms	44792 KB	Output is correct
20	Correct	301 ms	46380 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	31 ms	31992 KB	Output is correct
2	Correct	30 ms	31992 KB	Output is correct
3	Correct	30 ms	31944 KB	Output is correct
4	Correct	30 ms	31996 KB	Output is correct
5	Correct	31 ms	31992 KB	Output is correct
6	Correct	30 ms	31916 KB	Output is correct
7	Correct	30 ms	31992 KB	Output is correct
8	Correct	47 ms	31984 KB	Output is correct
9	Correct	70 ms	31968 KB	Output is correct
10	Correct	30 ms	31864 KB	Output is correct
11	Correct	286 ms	46696 KB	Output is correct
12	Correct	298 ms	46476 KB	Output is correct
13	Correct	304 ms	45652 KB	Output is correct
14	Correct	309 ms	45748 KB	Output is correct
15	Correct	332 ms	46836 KB	Output is correct
16	Correct	320 ms	45816 KB	Output is correct
17	Correct	325 ms	45916 KB	Output is correct
18	Correct	245 ms	47808 KB	Output is correct
19	Correct	277 ms	44792 KB	Output is correct
20	Correct	301 ms	46380 KB	Output is correct
21	Correct	365 ms	55664 KB	Output is correct
22	Correct	384 ms	55860 KB	Output is correct
23	Correct	445 ms	54896 KB	Output is correct
24	Correct	441 ms	54636 KB	Output is correct
25	Correct	401 ms	56928 KB	Output is correct
26	Correct	470 ms	55160 KB	Output is correct
27	Correct	477 ms	55160 KB	Output is correct
28	Correct	295 ms	57768 KB	Output is correct
29	Correct	361 ms	53624 KB	Output is correct
30	Correct	377 ms	55800 KB	Output is correct
31	Correct	437 ms	55800 KB	Output is correct
32	Correct	431 ms	55672 KB	Output is correct
33	Correct	382 ms	54520 KB	Output is correct
34	Correct	475 ms	54844 KB	Output is correct
35	Correct	479 ms	55124 KB	Output is correct
36	Correct	285 ms	53752 KB	Output is correct
37	Correct	364 ms	55672 KB	Output is correct
38	Correct	484 ms	53688 KB	Output is correct
39	Correct	436 ms	55032 KB	Output is correct
40	Correct	449 ms	54832 KB	Output is correct

Subtask #4
0 / 53.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	31 ms	31992 KB	Output is correct
2	Correct	30 ms	31992 KB	Output is correct
3	Correct	30 ms	31944 KB	Output is correct
4	Correct	30 ms	31996 KB	Output is correct
5	Correct	31 ms	31992 KB	Output is correct
6	Correct	30 ms	31916 KB	Output is correct
7	Correct	30 ms	31992 KB	Output is correct
8	Correct	47 ms	31984 KB	Output is correct
9	Correct	70 ms	31968 KB	Output is correct
10	Correct	30 ms	31864 KB	Output is correct
11	Execution timed out	2043 ms	46700 KB	Time limit exceeded
12	Halted	0 ms	0 KB	-

Subtask #5
0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	31 ms	31992 KB	Output is correct
2	Correct	30 ms	31992 KB	Output is correct
3	Correct	30 ms	31944 KB	Output is correct
4	Correct	30 ms	31996 KB	Output is correct
5	Correct	31 ms	31992 KB	Output is correct
6	Correct	30 ms	31916 KB	Output is correct
7	Correct	30 ms	31992 KB	Output is correct
8	Correct	47 ms	31984 KB	Output is correct
9	Correct	70 ms	31968 KB	Output is correct
10	Correct	30 ms	31864 KB	Output is correct
11	Correct	286 ms	46696 KB	Output is correct
12	Correct	298 ms	46476 KB	Output is correct
13	Correct	304 ms	45652 KB	Output is correct
14	Correct	309 ms	45748 KB	Output is correct
15	Correct	332 ms	46836 KB	Output is correct
16	Correct	320 ms	45816 KB	Output is correct
17	Correct	325 ms	45916 KB	Output is correct
18	Correct	245 ms	47808 KB	Output is correct
19	Correct	277 ms	44792 KB	Output is correct
20	Correct	301 ms	46380 KB	Output is correct
21	Correct	365 ms	55664 KB	Output is correct
22	Correct	384 ms	55860 KB	Output is correct
23	Correct	445 ms	54896 KB	Output is correct
24	Correct	441 ms	54636 KB	Output is correct
25	Correct	401 ms	56928 KB	Output is correct
26	Correct	470 ms	55160 KB	Output is correct
27	Correct	477 ms	55160 KB	Output is correct
28	Correct	295 ms	57768 KB	Output is correct
29	Correct	361 ms	53624 KB	Output is correct
30	Correct	377 ms	55800 KB	Output is correct
31	Correct	437 ms	55800 KB	Output is correct
32	Correct	431 ms	55672 KB	Output is correct
33	Correct	382 ms	54520 KB	Output is correct
34	Correct	475 ms	54844 KB	Output is correct
35	Correct	479 ms	55124 KB	Output is correct
36	Correct	285 ms	53752 KB	Output is correct
37	Correct	364 ms	55672 KB	Output is correct
38	Correct	484 ms	53688 KB	Output is correct
39	Correct	436 ms	55032 KB	Output is correct
40	Correct	449 ms	54832 KB	Output is correct
41	Execution timed out	2043 ms	46700 KB	Time limit exceeded
42	Halted	0 ms	0 KB	-

Submission #159806

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