Submission #154147

#	Time	Username	Problem	Language	Result	Execution time	Memory
154147		ryansee	Snake Escaping (JOI18_snake_escaping)	C++14	75 / 100	2050 ms	65536 KiB

snake_escaping

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

#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define pb push_back
#define eb emplace_back
#define ins insert
#define ph push
#define f first
#define s second
#define cbr cerr << "hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ((ll)x.size())
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
#define btinpct(x) __builtin_popcountll((x))
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());    //can be used by calling rng() or shuffle(A, A+n, rng)
inline long long rand(long long x, long long y) { return (rng() % (y+1-x)) + x; } //inclusivesss
string to_string(char c) {string s(1,c);return s;} template<typename T> inline T gcd(T a,T b){if(a>b)swap(a,b);if(a==0)return b;return gcd(b%a,a);}

#define ll long long //int 
#define ld long double
#define FOR(ii, ss, ee) for(ll ii = (ss); ii <= (ll)(ee); ++ii)
#define DEC(ii, ss, ee) for(ll ii = (ss); ii >= (ll)(ee); --ii)
typedef pair <ll, ll> pi; typedef pair <ll, pi> spi; typedef pair <pi, pi> dpi;

#define LLINF ((long long) 1e18)//1234567890987654321
#define INF 1234567890ll
// #define cerr if(0)cout
#define MAXN (20)
#define int long long
int L, Q, pow3[MAXN];
string S,A;
int ans[1<<MAXN];
int mid=7;
int val[1<<(MAXN-7)];
int dp[1594323 + 2], lastqnm[1594323 + 2];
pi q[1<<MAXN];
string gug(ll x, ll place) {
	string res="";
	while(place --) {
		res+=to_string(x%3);
		x /= 3;
	}
	reverse(all(res));
	return res;
}
int32_t main()
{
	FAST
	cin>>L>>Q; mid=min(mid, L);
	cin>>S;
	pow3[0]=1;FOR(i,1,MAXN-1)pow3[i]=pow3[i-1]*3ll; 
	FOR(ii,0,Q-1) { cin>>A; reverse(all(A)); 
		FOR(i,0,min(L,mid)-1) {
			if(A[i] == '0' || A[i] == '?') q[ii].f |= (1<<(2*i));
			if(A[i] == '1' || A[i] == '?') q[ii].f |= (1<<(2*i+1));
		}
		FOR(i,min(L,mid),L-1) {
			q[ii].s += pow3[i-min(L,mid)] * (A[i] == '?' ? 2 : (A[i] - '0'));
		}
	}
	mmst(lastqnm, -1);
	FOR(i,0,pow3[max(0ll,L-mid)]-1) {
		int n=i;
		FOR(j,0,L-mid-1) {
			if(n % 3 == 2) lastqnm[i] = j;
			n /= 3;
		}
	}
	FOR(i,0,(1<<mid)-1) {
		mmst(val, 0); FOR(j,0,pow3[max(0ll,L-mid)]-1) dp[j]=0;
		if(L >= mid) FOR(j,0,(1<<(L-mid))-1) {
			int c=0;
			FOR(k,0,L-mid-1) {
				if(j & (1<<k)) c += pow3[k];
			}
			dp[c] = S[i + (j << mid)] - '0';
		}
		if(L < mid) dp[0] = S[i]-'0';
		if(L >= mid) FOR(j,0,pow3[L-mid]-1) if(~lastqnm[j]) {
			dp[j] = dp[j-pow3[lastqnm[j]]] + dp[j-2*pow3[lastqnm[j]]]; // a base dp val will have lastqnm == -1
		}
		ll tomeet=0;
		FOR(j,0,min(L, mid)-1) {
			if( (1<<j) & i) tomeet |= (1<<(j*2+1));
			else tomeet |= (1<<(j*2));
		}
		FOR(ii,0,Q-1) {
			if( (q[ii].f & tomeet) == tomeet) ans[ii] += dp[q[ii].s];
		}
	}
	FOR(ii,0,Q-1) cout<<ans[ii]<<"\n";
}

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