This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<int, int>;
#define foru(i, l, r) for(int i=(l); i<=(r); ++i)
#define ford(i, l, r) for(int i=(l); i>=(r); --i)
#define fore(x, v) for(auto &x : v)
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define fi first
#define se second
#define file "input"
template<class T> bool minimize(T &a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<class T> bool maximize(T &a, T b) { if (a < b) { a = b; return 1; } return 0; }
void setIO() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
if (fopen(file".inp", "r")) {
freopen(file".inp", "r", stdin);
freopen(file".out", "w", stdout);
}
}
const int N = 20;
int n, q, full;
char a[1<<20];
int sum[1<<20], rsum[1<<20];
int main() {
setIO();
cin >> n >> q;
full = (1<<n)-1;
foru(i, 0, full) cin >> a[i];
foru(i, 0, full) {
a[i] -= '0';
sum[i] = a[i];
rsum[i] = a[i];
}
foru(bt, 0, n-1) {
foru(i, 0, full) {
if (i >> bt & 1)
sum[i] += sum[i-(1<<bt)];
else
rsum[i] += rsum[i+(1<<bt)];
}
}
int cap = n/3;
while (q--) {
string s;
cin >> s;
reverse(all(s));
int cnt[3] = {}, ans = 0, ma = 0, mb = 0, mc = 0;
foru(i, 0, n-1) {
if (s[i] == '?') { cnt[0] += 1; ma += 1 << i; }
else if (s[i] == '1') { cnt[1] += 1; mb += 1 << i; }
else { cnt[2] += 1; mc += 1 << i; }
}
if (cnt[0] <= cap) {
for(int i=ma; ; i=(i-1)&ma) {
ans += a[mb|i];
if (i == 0) break;
}
}
else if (cnt[1] <= cap) {
for(int i=mb; ; i=(i-1)&mb) {
if ((cnt[1]-__builtin_popcount(i)) & 1) ans -= sum[ma|i];
else ans += sum[ma|i];
if (i == 0) break;
}
}
else {
for(int i=mc; ; i=(i-1)&mc) {
if (__builtin_popcount(i) & 1) ans -= rsum[mb|i];
else ans += rsum[mb|i];
if (i == 0) break;
}
}
cout << ans << "\n";
}
}
Compilation message (stderr)
snake_escaping.cpp: In function 'void setIO()':
snake_escaping.cpp:22:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
22 | freopen(file".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
snake_escaping.cpp:23:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
23 | freopen(file".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |