oj.uz

답안 #159806

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
159806 2019-10-24T20:32:06 Z GioChkhaidze Snake Escaping (JOI18_snake_escaping) C++14
22 / 100
 2000 ms 57768 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -