Submission #160130

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
160130	2019-10-26T06:00:15 Z	GioChkhaidze	Snake Escaping (JOI18_snake_escaping)	C++14	22 / 100	658 ms	23932 KB

snake_escaping

#include <bits/stdc++.h>
using namespace std;

const int Q=1e6+5;
const int M20=1048576;
const int M13=1594323;

int n,q,C[M20+5],M[20],dp[M13+5],ANS[Q],Y[Q],Last2[M13+5];	
bool Bo[Q][(1<<7)+5];

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) {	
		if (n==8) cout<<1/0<<endl;
	
		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);
		
		for (int i=1; i<=q; i++) {
			string S;
			cin>>S;	
			
			for (int k=S.size()-1; k>=K; k--) {
				if (S[k]=='?') Y[i]+=2*M[k-S.size()+1];	
					else
				if (S[k]=='1') Y[i]+=M[k-S.size()+1];
			}
			
			int Bit=0;
			for (int k=0; k<K; k++) 
				if (S[k]=='1') Bit+=(1<<k);

			for (int j=0; j<(1<<K); j++) 
				if (j&Bit==Bit) Bo[i][j]=1;
		}
		
		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:11:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () { 
       ^
snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:20:20: warning: division by zero [-Wdiv-by-zero]
   if (n==8) cout<<1/0<<endl;
                   ~^~
snake_escaping.cpp:46:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int j=0; j<s.size(); j++) 
                  ~^~~~~~~~~
snake_escaping.cpp:78:14: warning: self-comparison always evaluates to true [-Wtautological-compare]
     if (j&Bit==Bit) Bo[i][j]=1;
           ~~~^~~~~
snake_escaping.cpp:78:14: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
snake_escaping.cpp:102:9: warning: unused variable 'x' [-Wunused-variable]
     int x=j;
         ^

Subtask #1
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	632 KB	Output is correct
2	Correct	8 ms	632 KB	Output is correct
3	Correct	4 ms	632 KB	Output is correct
4	Correct	4 ms	632 KB	Output is correct
5	Correct	4 ms	632 KB	Output is correct
6	Correct	4 ms	632 KB	Output is correct
7	Correct	4 ms	604 KB	Output is correct
8	Correct	6 ms	572 KB	Output is correct
9	Correct	4 ms	632 KB	Output is correct
10	Correct	4 ms	632 KB	Output is correct

Subtask #2
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	632 KB	Output is correct
2	Correct	8 ms	632 KB	Output is correct
3	Correct	4 ms	632 KB	Output is correct
4	Correct	4 ms	632 KB	Output is correct
5	Correct	4 ms	632 KB	Output is correct
6	Correct	4 ms	632 KB	Output is correct
7	Correct	4 ms	604 KB	Output is correct
8	Correct	6 ms	572 KB	Output is correct
9	Correct	4 ms	632 KB	Output is correct
10	Correct	4 ms	632 KB	Output is correct
11	Correct	259 ms	4728 KB	Output is correct
12	Correct	289 ms	4320 KB	Output is correct
13	Correct	308 ms	3728 KB	Output is correct
14	Correct	285 ms	3704 KB	Output is correct
15	Correct	285 ms	4688 KB	Output is correct
16	Correct	300 ms	3832 KB	Output is correct
17	Correct	325 ms	3832 KB	Output is correct
18	Correct	255 ms	5632 KB	Output is correct
19	Correct	248 ms	2552 KB	Output is correct
20	Correct	291 ms	4344 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	632 KB	Output is correct
2	Correct	8 ms	632 KB	Output is correct
3	Correct	4 ms	632 KB	Output is correct
4	Correct	4 ms	632 KB	Output is correct
5	Correct	4 ms	632 KB	Output is correct
6	Correct	4 ms	632 KB	Output is correct
7	Correct	4 ms	604 KB	Output is correct
8	Correct	6 ms	572 KB	Output is correct
9	Correct	4 ms	632 KB	Output is correct
10	Correct	4 ms	632 KB	Output is correct
11	Correct	259 ms	4728 KB	Output is correct
12	Correct	289 ms	4320 KB	Output is correct
13	Correct	308 ms	3728 KB	Output is correct
14	Correct	285 ms	3704 KB	Output is correct
15	Correct	285 ms	4688 KB	Output is correct
16	Correct	300 ms	3832 KB	Output is correct
17	Correct	325 ms	3832 KB	Output is correct
18	Correct	255 ms	5632 KB	Output is correct
19	Correct	248 ms	2552 KB	Output is correct
20	Correct	291 ms	4344 KB	Output is correct
21	Correct	340 ms	10900 KB	Output is correct
22	Correct	357 ms	10816 KB	Output is correct
23	Correct	438 ms	9876 KB	Output is correct
24	Correct	432 ms	9812 KB	Output is correct
25	Correct	379 ms	11600 KB	Output is correct
26	Correct	447 ms	10192 KB	Output is correct
27	Correct	481 ms	10072 KB	Output is correct
28	Correct	261 ms	12668 KB	Output is correct
29	Correct	338 ms	8616 KB	Output is correct
30	Correct	363 ms	11000 KB	Output is correct
31	Correct	454 ms	10616 KB	Output is correct
32	Correct	444 ms	10696 KB	Output is correct
33	Correct	367 ms	9596 KB	Output is correct
34	Correct	439 ms	9592 KB	Output is correct
35	Correct	469 ms	10272 KB	Output is correct
36	Correct	259 ms	8824 KB	Output is correct
37	Correct	353 ms	10616 KB	Output is correct
38	Correct	340 ms	8696 KB	Output is correct
39	Correct	436 ms	9976 KB	Output is correct
40	Correct	430 ms	9720 KB	Output is correct

Subtask #4
0 / 53.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	632 KB	Output is correct
2	Correct	8 ms	632 KB	Output is correct
3	Correct	4 ms	632 KB	Output is correct
4	Correct	4 ms	632 KB	Output is correct
5	Correct	4 ms	632 KB	Output is correct
6	Correct	4 ms	632 KB	Output is correct
7	Correct	4 ms	604 KB	Output is correct
8	Correct	6 ms	572 KB	Output is correct
9	Correct	4 ms	632 KB	Output is correct
10	Correct	4 ms	632 KB	Output is correct
11	Incorrect	658 ms	23932 KB	Output isn't correct
12	Halted	0 ms	0 KB	-

Subtask #5
0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	632 KB	Output is correct
2	Correct	8 ms	632 KB	Output is correct
3	Correct	4 ms	632 KB	Output is correct
4	Correct	4 ms	632 KB	Output is correct
5	Correct	4 ms	632 KB	Output is correct
6	Correct	4 ms	632 KB	Output is correct
7	Correct	4 ms	604 KB	Output is correct
8	Correct	6 ms	572 KB	Output is correct
9	Correct	4 ms	632 KB	Output is correct
10	Correct	4 ms	632 KB	Output is correct
11	Correct	259 ms	4728 KB	Output is correct
12	Correct	289 ms	4320 KB	Output is correct
13	Correct	308 ms	3728 KB	Output is correct
14	Correct	285 ms	3704 KB	Output is correct
15	Correct	285 ms	4688 KB	Output is correct
16	Correct	300 ms	3832 KB	Output is correct
17	Correct	325 ms	3832 KB	Output is correct
18	Correct	255 ms	5632 KB	Output is correct
19	Correct	248 ms	2552 KB	Output is correct
20	Correct	291 ms	4344 KB	Output is correct
21	Correct	340 ms	10900 KB	Output is correct
22	Correct	357 ms	10816 KB	Output is correct
23	Correct	438 ms	9876 KB	Output is correct
24	Correct	432 ms	9812 KB	Output is correct
25	Correct	379 ms	11600 KB	Output is correct
26	Correct	447 ms	10192 KB	Output is correct
27	Correct	481 ms	10072 KB	Output is correct
28	Correct	261 ms	12668 KB	Output is correct
29	Correct	338 ms	8616 KB	Output is correct
30	Correct	363 ms	11000 KB	Output is correct
31	Correct	454 ms	10616 KB	Output is correct
32	Correct	444 ms	10696 KB	Output is correct
33	Correct	367 ms	9596 KB	Output is correct
34	Correct	439 ms	9592 KB	Output is correct
35	Correct	469 ms	10272 KB	Output is correct
36	Correct	259 ms	8824 KB	Output is correct
37	Correct	353 ms	10616 KB	Output is correct
38	Correct	340 ms	8696 KB	Output is correct
39	Correct	436 ms	9976 KB	Output is correct
40	Correct	430 ms	9720 KB	Output is correct
41	Incorrect	658 ms	23932 KB	Output isn't correct
42	Halted	0 ms	0 KB	-

Submission #160130

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