Submission #1278151

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278151		PlayVoltz	Snake Escaping (JOI18_snake_escaping)	C++20	100 / 100	454 ms	34180 KiB

snake_escaping

#include <cstdio>
#include <stdio.h>
#include <stdbool.h>
#include <iostream>
#include <map>
#include <vector>
#include <climits>
#include <stack>
#include <string>
#include <queue>
#include <algorithm>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <cmath>
#include <cctype>
#include <bitset>
#include <iomanip>
#include <cstring>
#include <numeric>
#include <cassert>
#include <random>
using namespace std;
 
#define int long long
#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second

int32_t main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n, q;
	string s;
	cin>>n>>q>>s;
	vector<int> vect((1<<n)), sup((1<<n), 0), rsup((1<<n), 0);
	for (int i=0; i<(1<<n); ++i)vect[i]=sup[i]=rsup[i^((1<<n)-1)]=s[i]-'0';
	for (int i=0; i<n; ++i)for (int mask=0; mask<(1<<n); ++mask)if (!(mask&(1<<i)))sup[mask]+=sup[mask^(1<<i)], rsup[mask]+=rsup[mask^(1<<i)];
	while (q--){
		cin>>s;
		reverse(s.begin(), s.end());
		int a=0, b=0, c=0, aa=0, bb=0, cc=0, res=0;
		for (int i=0; i<n; ++i){
			if (s[i]=='0')++aa, a|=(1<<i);
			else if (s[i]=='1')++bb, b|=(1<<i);
			else ++cc, c|=(1<<i);
		}
		if (min({aa, bb, cc})==aa){
			for (int mask=a; mask; mask=(mask-1)&a)res+=(1-2*(__builtin_popcount(mask)%2))*sup[mask|b];
			res+=sup[b];
		}
		else if (min(bb, cc)==bb){
			for (int mask=b; mask; mask=(mask-1)&b)res+=(1-2*(__builtin_popcount(mask)%2))*rsup[mask|a];
			res+=rsup[a];
		}
		else{
			for (int mask=c; mask; mask=(mask-1)&c)res+=vect[b|mask];
			res+=vect[b];
		}
		cout<<res<<"\n";
	}
}

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