#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#define taskname "test"
#define fi first
#define se second
#define pb push_back
#define faster ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
using ll = long long;
using ull = unsigned ll;
using ld = long double;
using pii = pair <int, int>;
using pil = pair <int, ll>;
using pli = pair <ll, int>;
using pll = pair <ll, ll>;
mt19937 Rand(chrono::steady_clock::now().time_since_epoch().count());
ll min(const ll &a, const ll &b){
return (a < b) ? a : b;
}
ll max(const ll &a, const ll &b){
return (a > b) ? a : b;
}
//const ll Mod = 1000000007;
//const ll Mod2 = 999999999989;
//only use when required
const int maxN = 20;
int n, q;
string s, t;
int dp[(1 << maxN) + 2];
int f[(1 << maxN) + 2];
int cnt[(1 << maxN) + 2];
void WriteInt(int x)
{
if (x > 9)
WriteInt(x / 10);
putchar(x % 10 + '0');
}
inline int inv(int i){
return ((1 << n) - 1) ^ i;
}
void Init(){
cin >> n >> q >> s;
for (int i = 0; i < int(s.length()); ++i){
dp[i] = s[i] - '0';
f[inv(i)] = dp[i];
}
for (int i = 0; i < n; ++i){
for (int j = 1; j < 1 << n; ++j){
if (j & (1 << i)){
dp[j] += dp[j ^ (1 << i)];
}
}
}
for (int i = 0; i < n; ++i){
for (int j = 0; j < 1 << n; ++j){
if (j & (1 << i)){
f[j] += f[j ^ (1 << i)];
}
}
}
for (int i = 1; i < 1 << n; ++i){
int j = i & -i;
cnt[i] = cnt[i ^ j] + 1;
}
int x, y, z;
int mask1, mask0, tem;
while (q--){
cin >> t;
x = y = z = mask1 = mask0 = tem = 0;
vector <int> val((1 << n) + 1, 0);
reverse(t.begin(), t.end());
for (int i = 0; i < n; ++i){
if (t[i] == '0') ++x, mask0 ^= 1 << i;
if (t[i] == '1') ++y, mask1 ^= 1 << i;
if (t[i] == '?') ++z, tem ^= 1 << i;
}
if (x <= n / 3){
int ans = -f[tem];
for (int i = mask0; i; i = (i - 1) & mask0){
if (cnt[i] & 1) ans += f[i + tem];
else ans -= f[i + tem];
}
ans = abs(ans);
WriteInt(ans);
putchar('\n');
}
else if (y <= n / 3){
int ans = -dp[tem];
for (int i = mask1; i; i = (i - 1) & mask0){
if (cnt[i] & 1) ans += dp[i + tem];
else ans -= dp[i + tem];
}
ans = abs(ans);
WriteInt(ans);
putchar('\n');
}
else{
//brute all ?s
int ans = s[mask1] - '0';
for (int i = tem; i; i = (i - 1) & tem){
ans += s[i + mask1] - '0';
}
WriteInt(ans);
putchar('\n');
}
}
}
int main(){
if (fopen(taskname".inp", "r")){
freopen(taskname".inp", "r", stdin);
//freopen(taskname".out", "w", stdout);
}
faster;
ll tt = 1;
//cin >> tt;
while (tt--){
Init();
}
}
Compilation message
snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:121:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
121 | freopen(taskname".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
344 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
344 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
344 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
344 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
344 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
