oj.uz

답안 #160130

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
160130 2019-10-26T06:00:15 Z GioChkhaidze Snake Escaping (JOI18_snake_escaping) C++14
22 / 100
 658 ms 23932 KB 
#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

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

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

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

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

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