답안 #160128

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
160128 2019-10-26T05:56:34 Z GioChkhaidze Snake Escaping (JOI18_snake_escaping) C++14
22 / 100
470 ms 49656 KB
#include <bits/stdc++.h>
using namespace std;
int n,q,C[(1<<21)],M[20],dp[2594323],ANS[1000006],Y[1000006],vs;
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)+5];
		
		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;
		}
		
		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:4:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () { 
       ^
snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:38: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:98:9: warning: unused variable 'x' [-Wunused-variable]
     int x=j;
         ^
# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 632 KB Output is correct
2 Correct 4 ms 632 KB Output is correct
3 Correct 4 ms 632 KB Output is correct
4 Correct 4 ms 636 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 632 KB Output is correct
8 Correct 4 ms 632 KB Output is correct
9 Correct 12 ms 632 KB Output is correct
10 Correct 4 ms 632 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 632 KB Output is correct
2 Correct 4 ms 632 KB Output is correct
3 Correct 4 ms 632 KB Output is correct
4 Correct 4 ms 636 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 632 KB Output is correct
8 Correct 4 ms 632 KB Output is correct
9 Correct 12 ms 632 KB Output is correct
10 Correct 4 ms 632 KB Output is correct
11 Correct 254 ms 4824 KB Output is correct
12 Correct 270 ms 4280 KB Output is correct
13 Correct 278 ms 3528 KB Output is correct
14 Correct 289 ms 3576 KB Output is correct
15 Correct 283 ms 4728 KB Output is correct
16 Correct 290 ms 3960 KB Output is correct
17 Correct 295 ms 3708 KB Output is correct
18 Correct 206 ms 5624 KB Output is correct
19 Correct 249 ms 2776 KB Output is correct
20 Correct 269 ms 4344 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 632 KB Output is correct
2 Correct 4 ms 632 KB Output is correct
3 Correct 4 ms 632 KB Output is correct
4 Correct 4 ms 636 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 632 KB Output is correct
8 Correct 4 ms 632 KB Output is correct
9 Correct 12 ms 632 KB Output is correct
10 Correct 4 ms 632 KB Output is correct
11 Correct 254 ms 4824 KB Output is correct
12 Correct 270 ms 4280 KB Output is correct
13 Correct 278 ms 3528 KB Output is correct
14 Correct 289 ms 3576 KB Output is correct
15 Correct 283 ms 4728 KB Output is correct
16 Correct 290 ms 3960 KB Output is correct
17 Correct 295 ms 3708 KB Output is correct
18 Correct 206 ms 5624 KB Output is correct
19 Correct 249 ms 2776 KB Output is correct
20 Correct 269 ms 4344 KB Output is correct
21 Correct 341 ms 10736 KB Output is correct
22 Correct 370 ms 10740 KB Output is correct
23 Correct 415 ms 9892 KB Output is correct
24 Correct 406 ms 9696 KB Output is correct
25 Correct 379 ms 11732 KB Output is correct
26 Correct 444 ms 10168 KB Output is correct
27 Correct 459 ms 10188 KB Output is correct
28 Correct 266 ms 12664 KB Output is correct
29 Correct 338 ms 8696 KB Output is correct
30 Correct 352 ms 10840 KB Output is correct
31 Correct 419 ms 10628 KB Output is correct
32 Correct 432 ms 10744 KB Output is correct
33 Correct 374 ms 9624 KB Output is correct
34 Correct 429 ms 9924 KB Output is correct
35 Correct 470 ms 10232 KB Output is correct
36 Correct 255 ms 8828 KB Output is correct
37 Correct 360 ms 10872 KB Output is correct
38 Correct 339 ms 8712 KB Output is correct
39 Correct 429 ms 9952 KB Output is correct
40 Correct 413 ms 9688 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 632 KB Output is correct
2 Correct 4 ms 632 KB Output is correct
3 Correct 4 ms 632 KB Output is correct
4 Correct 4 ms 636 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 632 KB Output is correct
8 Correct 4 ms 632 KB Output is correct
9 Correct 12 ms 632 KB Output is correct
10 Correct 4 ms 632 KB Output is correct
11 Runtime error 101 ms 49656 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 632 KB Output is correct
2 Correct 4 ms 632 KB Output is correct
3 Correct 4 ms 632 KB Output is correct
4 Correct 4 ms 636 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 632 KB Output is correct
8 Correct 4 ms 632 KB Output is correct
9 Correct 12 ms 632 KB Output is correct
10 Correct 4 ms 632 KB Output is correct
11 Correct 254 ms 4824 KB Output is correct
12 Correct 270 ms 4280 KB Output is correct
13 Correct 278 ms 3528 KB Output is correct
14 Correct 289 ms 3576 KB Output is correct
15 Correct 283 ms 4728 KB Output is correct
16 Correct 290 ms 3960 KB Output is correct
17 Correct 295 ms 3708 KB Output is correct
18 Correct 206 ms 5624 KB Output is correct
19 Correct 249 ms 2776 KB Output is correct
20 Correct 269 ms 4344 KB Output is correct
21 Correct 341 ms 10736 KB Output is correct
22 Correct 370 ms 10740 KB Output is correct
23 Correct 415 ms 9892 KB Output is correct
24 Correct 406 ms 9696 KB Output is correct
25 Correct 379 ms 11732 KB Output is correct
26 Correct 444 ms 10168 KB Output is correct
27 Correct 459 ms 10188 KB Output is correct
28 Correct 266 ms 12664 KB Output is correct
29 Correct 338 ms 8696 KB Output is correct
30 Correct 352 ms 10840 KB Output is correct
31 Correct 419 ms 10628 KB Output is correct
32 Correct 432 ms 10744 KB Output is correct
33 Correct 374 ms 9624 KB Output is correct
34 Correct 429 ms 9924 KB Output is correct
35 Correct 470 ms 10232 KB Output is correct
36 Correct 255 ms 8828 KB Output is correct
37 Correct 360 ms 10872 KB Output is correct
38 Correct 339 ms 8712 KB Output is correct
39 Correct 429 ms 9952 KB Output is correct
40 Correct 413 ms 9688 KB Output is correct
41 Runtime error 101 ms 49656 KB Execution killed with signal 11 (could be triggered by violating memory limits)
42 Halted 0 ms 0 KB -