Submission #160163

#	Time	Username	Problem	Language	Result	Execution time	Memory
160163		GioChkhaidze	Snake Escaping (JOI18_snake_escaping)	C++14	100 / 100	1646 ms	60304 KiB

snake_escaping

#pragma GCC optimize ("O3")
#pragma GCC optimize ("Ofast")
#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[15],dp[M13+5],ANS[Q],Y[Q],Last2[M13+5],Boz[Q],Boz2[Q],x,ko,K,i,j,k,Mid;	
string S,s;
char c;
main () { 
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>q;
	
	M[0]=1;
	for (int i=1; i<=13; i++) 
		M[i]=M[i-1]*3;
	
	Mid=min(n,13);
	
	for (i=0; i<(1<<n); i++) {
		cin>>c;
		C[i]=c-'0';
	}
	
	K=(n-Mid);
	for (i=1; i<=q; i++) {
		cin>>S;
		
		for (k=S.size()-1; k>=K; k--) {
			if (S[k]=='?') Y[i]+=2*M[S.size()-1-k];	
				else
			if (S[k]=='1') Y[i]+=M[S.size()-1-k];
		}
		
		for (k=0; k<K; k++)
			if (S[K-k-1]=='?') Boz2[i]|=(1<<(k));
				else
			if (S[K-k-1]=='1') Boz[i]|=(1<<(k));
	}
	
	for (i=0; i<M[Mid]; i++) {
		x=i,Last2[i]=-1;
		for (j=Mid-1; j>=0; j--) 
			if (x>=2*M[j]) { Last2[i]=j; break; }
				else
  			if (x>=M[j]) x-=M[j];
		}
		
	for (i=0; i<(1<<K); i++) {
		for (j=0; j<(1<<Mid); j++) {
			x=0;
			for (k=0; k<Mid; k++) 
				if (j&(1<<k)) x+=M[k];
			dp[x]=C[i*(1<<Mid)+j];
		}
			
		for (j=0; j<M[Mid]; j++) 
			if (Last2[j]!=-1) dp[j]=(dp[j-2*M[Last2[j]]]+dp[j-M[Last2[j]]]);	
		for (j=1; j<=q; j++) 
			if (!((i-(i&Boz2[j]))^Boz[j]))  ANS[j]+=dp[Y[j]];
	}
		
	for (i=1; i<=q; i++) 
		printf("%d\n",ANS[i]);			
}

Compilation message (stderr)

snake_escaping.cpp:11:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () { 
       ^

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 10 / 10
• Subtask 4: 53 / 53
• Subtask 5: 25 / 25