Submission #1034851

#	Time	Username	Problem	Language	Result	Execution time	Memory
1034851		1L1YA	Snake Escaping (JOI18_snake_escaping)	C++17	100 / 100	545 ms	39152 KiB

snake_escaping

//1L1YA

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

//#pragma GCC optimize ("O3,unrool-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

typedef long long       ll;
typedef pair<ll,ll>     pll;
typedef pair<int,int>   pii;

#define Pb              push_back
#define F               first
#define S               second
#define endl            '\n'
#define sep             ' '
#define all(x)          x.begin(),x.end()
#define al(x,n)         x+1,x+n+1
#define SZ(x)           ((int)x.size())
#define lc              (id<<1)
#define rc              (lc|1)
#define mid             (l+r>>1)
#define dokme(x)        cout << x << endl, exit(0)
#define sik(x)          cout << x << endl;continue;
#define pc              __builtin_popcount
#define FastIO          ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define FileIO          freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll oo=1e18;
const int mod=1e9+7;
const int inf=1e9+111;
const int N=20;

int n,q,dp[2][1<<N];
string s;

int main(){
	FastIO

	cin >> n >> q >> s;
	for(int i=0;i<1<<n;i++)	dp[0][i]=dp[1][i]=s[i]-'0';
	for(int i=0;i<n;i++)
		for(int mask=0;mask<1<<n;mask++)
			if(!(mask>>i & 1))
				dp[0][mask]+=dp[0][mask^(1<<i)];
	for(int i=0;i<n;i++)
		for(int mask=(1<<n)-1;~mask;mask--)
			if(mask>>i & 1)
				dp[1][mask]+=dp[1][mask^(1<<i)];
	while(q--){
		int ans=0,msk0=0,msk1=0,msk2=0;
		string t;cin >> t;
		for(char c: t){
			msk0<<=1;msk1<<=1;msk2<<=1;
			if(c=='0')	msk0++;
			else if(c=='1')	msk1++;
			else	msk2++;
		}
		if(pc(msk0)<=6){
			for(int mask=msk0;;mask=(mask-1)&msk0){
				ans+=(pc(mask)&1?-1:1)*dp[0][mask^msk1];
				if(!mask)	break;
			}
		}
		else if(pc(msk1)<=6){
			for(int mask=msk1;;mask=(mask-1)&msk1){
				ans+=((pc(msk1)-pc(mask))&1?-1:1)*dp[1][mask^msk2];
				if(!mask)	break;
			}
		}
		else{
			for(int mask=msk2;;mask=(mask-1)&msk2){
				ans+=s[mask|msk1]-'0';
				if(!mask)	break;
			}
		}
		cout << ans << endl;
	}

	return 0;
}

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