# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
735817 | lovrot | Snake Escaping (JOI18_snake_escaping) | C++17 | 1910 ms | 46300 KiB |
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 <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <algorithm>
#define X first
#define Y second
#define pb push_back
using namespace std;
typedef pair<int, int> pii;
const int LOG = 20;
const int OFF = 1 << LOG;
int n, m, P[OFF], sum;
int POP[OFF], SUB[OFF], HIP[OFF];
int count(int mask) {
return __builtin_popcount(mask);
}
int main() {
scanf("%d%d", &n, &m);
int off = 1 << n;
for(int i = 0; i < off; i++) {
char c;
scanf(" %c", &c);
P[i] = c - '0';
SUB[i] = HIP[i] = P[i];
sum += P[i];
POP[i] = count(i);
}
for(int i = 0; i < n; i++)
for(int mask = 0; mask < off; mask++) {
if(mask & 1 << i) SUB[mask] += SUB[mask ^ 1 << i];
else HIP[mask] += HIP[mask ^ 1 << i];
}
for(int t = 0; t < m; t++) {
int zer = 0;
int one = 0;
int que = 0;
for(int i = 0, j = n - 1; i < n; i++, j--) {
char c;
scanf(" %c", &c);
if(c == '?') que |= 1 << j;
else if (c == '1') one |= 1 << j;
else zer |= 1 << j;
}
int nim = min({POP[zer], POP[que], POP[one]});
int sol = 0;
if(POP[zer] == nim) { //0
for(int mask = zer; ; mask = (mask - 1) & zer) {
sol += (POP[mask] & 1 ? -1 : 1) * HIP[mask | one];
if(mask == 0) break;
}
} else if(POP[one] == nim) { //1
for(int mask = one; ; mask = (mask - 1) & one) {
sol += (POP[mask] & 1 ? -1 : 1) * SUB[que | (one ^ mask)];
if(mask == 0) break;
}
} else { //?
for(int mask = que; ; mask = (mask - 1) & que) {
sol += P[mask | one];
if(mask == 0) break;
}
}
printf("%d\n", sol);
}
return 0;
}
Compilation message (stderr)
# | 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... |