이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
void dbg_out() { cout << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }
#ifdef LOCAL
#define debug(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define debug(...) "zzz"
#endif
using ll = long long;
using ld = long double;
using pii = pair<ll,ll>;
#define FOR(i, n) for(int i = 1; i<=n; i++)
#define F0R(i, n) for(int i = 0; i<n; i++)
#define all(x) x.begin(), x.end()
#define mp make_pair
#define pb push_back
#define f first
#define s second
template<typename T, typename = void> struct is_iterable : false_type {};
template<typename T> struct is_iterable<T, void_t<decltype(begin(declval<T>())),decltype(end(declval<T>()))>> : true_type {};
template<typename T> typename enable_if<is_iterable<T>::value&&!is_same<T, string>::value,ostream&>::type operator<<(ostream &cout, T const &v);
template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "(" << p.f << ", " << p.s << ")"; }
template<typename T> typename enable_if<is_iterable<T>::value&&!is_same<T, string>::value,ostream&>::type operator<<(ostream &cout, T const &v) {
cout << "[";
for (auto it = v.begin(); it != v.end();) {
cout << *it;
if (++it != v.end()) cout << ", ";
}
return cout << "]";
}
//var
ll T;
void solve() {
ll n, q;
string a;
cin >> n >> q >> a;
debug(n, q, a);
vector<ll> sub(1 << n), super(1 << n);
ll big = (1LL << n) - 1;
F0R (i, 1 << n) {
sub[i] = a[i] - '0';
super[i ^ big] = a[i] - '0';
}
F0R (i, n) F0R (msk, 1 << n) if ((msk >> i) & 1) {
sub[msk] += sub[msk ^ (1 << i)];
super[msk] += super[msk ^ (1 << i)];
}
vector new_super = super;
F0R (msk, 1 << n) {
new_super[big ^ msk] = super[msk];
}
swap(new_super, super);
new_super.clear();
//debug(super);
//debug(super[1]);;
//debug(super);
//debug(sub);
while (q--) {
string t; cin >> t;
reverse(all(t));
int zc = 0, oc = 0, qc = 0;
for (auto u : t) {
if (u == '0') {
zc++;
} else if (u == '1') {
oc++;
} else {
qc++;
}
}
ll qmsk = 0, omsk = 0, zmsk = 0;
F0R (i, n) if (t[i] == '?') {
qmsk |= 1LL << i;
}
F0R (i, n) if (t[i] == '1') {
omsk |= 1LL << i;
}
F0R (i, n) if (t[i] == '0') {
zmsk |= 1LL << i;
}
if (oc <= 6) {
//zeros fixed (sub)
ll ans = 0;
for (int i = omsk; i >= 0; i = (i - 1) & omsk) {
ll pie = (__builtin_popcount(i) % 2 == __builtin_popcount(omsk) % 2 ? 1 : -1);
ans += pie * sub[(i | qmsk)];
if (i == 0) break;
}
cout << ans << '\n';
} else if (zc <= 6) {
//ones fixed (super)
ll ans = 0;
for (int i = zmsk; i >= 0; i = (i - 1) & zmsk) {
ll pie = (__builtin_popcount(i) % 2 == 0 ? 1 : -1);
ans += pie * super[i | omsk];
//debug(ans, i | omsk);
if (i == 0) break;
}
cout << ans << '\n';
} else if (qc <= 6) {
ll ans = 0;
for (int i = qmsk; i >= 0; i = (i - 1) & qmsk) {
ans += a[qmsk | omsk] - '0';
if (i == 0) break;
}
cout << ans << '\n';
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
T = 1;
//cin >> T;
FOR(t, T)
solve();
cout.flush();
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
snake_escaping.cpp: In function 'void solve()':
snake_escaping.cpp:10:20: warning: statement has no effect [-Wunused-value]
10 | #define debug(...) "zzz"
| ^~~~~
snake_escaping.cpp:47:2: note: in expansion of macro 'debug'
47 | debug(n, q, a);
| ^~~~~
# | 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... |