이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
ll dp[1 << 20], dp2[1 << 20], ans;
char b[1 << 20], s[1 << 20];
int l, q;
void recurr1(int i, int num, int tot) {
if(i == l) {
if(tot & 1) ans -= dp[num];
else ans += dp[num];
return;
}
if(s[i] == '0') recurr1(++i, num << 1, tot);
else if(s[i] == '?') recurr1(++i, num << 1 | 1, tot);
else {
recurr1(++i, num << 1 | 1, tot);
recurr1(++i, num << 1, ++tot);
}
}
void recurr0(int i, int num, int tot) {
if(i == l) {
if(tot & 1) ans -= dp2[num];
else ans += dp2[num];
return;
}
if(s[i] == '1') recurr0(++i, num << 1 | 1, tot);
else if(s[i] == '?') recurr0(++i, num << 1, tot);
else {
recurr0(++i, num << 1, tot);
recurr0(++i, num << 1 | 1, ++tot);
}
}
void recurrw0t(int i, int num) {
if(i == l) {
ans += b[num] - '0';
return;
}
if(s[i] == '?') {
recurrw0t(++i, num << 1 | 1);
recurrw0t(++i, num << 1);
} else recurrw0t(++i, (num << 1) + (s[i] == '1'));
}
int main(int argc, char const *argv[]) {
#ifdef LOCAL_TESTING
freopen("in", "r", stdin);
#endif
scanf("%d %d", &l, &q);
scanf(" %s", b);
for(int i = 0; i < (1 << l); ++i)
dp[i] = dp2[i] = b[i] - '0';
for(int i = 0; i < l; ++i)
for(int j = 0; j < (1 << l); ++j)
if(j >> i & 1) dp[j] += dp[j ^ (1 << i)];
for(int i = 0; i < l; ++i)
for(int j = 0; j < (1 << l); ++j)
if(~j >> i & 1) dp2[j] += dp2[j | (1 << i)];
while(q--) {
scanf(" %s", s);
int n0 = 0, n1 = 0, nw0t = 0;
for(int i = 0; i < l; ++i) {
n0 += s[i] == '0';
n1 += s[i] == '1';
nw0t += s[i] == '?';
}
if(n1 == 0) {
int num = 0;
for(int i = 0; i < l; ++i)
num = (num << 1) + (s[i] == '?');
printf("%lld\n", dp[num]);
} else if(nw0t == 0) {
int num = 0;
for(int i = 0; i < l; ++i)
num = (num << 1) + (s[i] == '1');
printf("%c\n", b[num]);
} else {
ans = 0;
if(nw0t <= n1 && nw0t <= n0) recurrw0t(0, 0);
else if(n1 <= nw0t && n1 <= n0) recurr1(0, 0, 0);
else recurr0(0, 0, 0);
printf("%lld\n", ans);
}
}
}
컴파일 시 표준 에러 (stderr) 메시지
snake_escaping.cpp: In function 'void recurrw0t(int, int)':
snake_escaping.cpp:46:51: warning: operation on 'i' may be undefined [-Wsequence-point]
} else recurrw0t(++i, (num << 1) + (s[i] == '1'));
^
snake_escaping.cpp: In function 'int main(int, const char**)':
snake_escaping.cpp:53:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &l, &q);
^
snake_escaping.cpp:54:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %s", b);
^
snake_escaping.cpp:68:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %s", s);
^
# | 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... |