| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 675741 | 2022-12-27T19:29:36 Z | MilosMilutinovic | Snake Escaping (JOI18_snake_escaping) | C++17 | 2000 ms | 14636 KB |
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <array>
using namespace std;
#ifdef LOCAL
#define eprintf(...) {fprintf(stderr, __VA_ARGS__);fflush(stderr);}
#else
#define eprintf(...) 42
#endif
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
template<typename T>
using pair2 = pair<T, T>;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
return (ull)rng() % B;
}
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
clock_t startTime;
double getCurrentTime() {
return (double)(clock() - startTime) / CLOCKS_PER_SEC;
}
const int N = (1 << 21);
int n, q;
char s[N];
char t[N];
int sub[N];
int sup[N];
int main()
{
startTime = clock();
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
scanf("%d%d", &n, &q);
scanf("%s", s);
for (int i = 0; i < (1 << n); i++) {
sub[i] = (int)(s[i] - '0');
sup[i] = (int)(s[i] - '0');
}
for (int i = 0; i < n; i++)
for (int mask = 0; mask < (1 << n); mask++)
if (mask >> i & 1)
sub[mask] += sub[mask ^ (1 << i)];
for (int i = 0; i < n; i++)
for (int mask = (1 << n) - 1; mask >= 0; mask--)
if (!(mask >> i & 1))
sup[mask] += sup[mask ^ (1 << i)];
while(q--) {
scanf("%s", t);
reverse(t, t + n);
vector<int> zero, one, qmark;
for (int i = 0; i < n; i++) {
if (t[i] == '0') zero.push_back(i);
if (t[i] == '1') one.push_back(i);
if (t[i] == '?') qmark.push_back(i);
}
int tmask = 0;
for (int i = 0; i < n; i++)
if (t[i] == '1')
tmask += (1 << i);
int ans = 0;
if (qmark.size() <= 6) {
int sz = qmark.size();
for (int mask = 0; mask < (1 << sz); mask++) {
int nmask = tmask;
for (int i = 0; i < sz; i++)
if (mask >> i & 1)
nmask += (1 << qmark[i]);
ans += (int)(s[nmask] - '0');
}
} else if (zero.size() <= 6) {
int sz = zero.size();
for (int mask = 0; mask < (1 << sz); mask++) {
int nmask = tmask;
for (int i = 0; i < sz; i++)
if (mask >> i & 1)
nmask += (1 << zero[i]);
ans += sup[nmask] * (__builtin_popcount(mask) % 2 == 0 ? 1 : -1);
}
} else {
assert(one.size() <= 6);
int sz = one.size();
tmask = 0;
for (int i = 0; i < n; i++)
if (t[i] == '?')
tmask += (1 << i);
for (int mask = 0; mask < (1 << sz); mask++) {
int nmask = tmask;
for (int i = 0; i < sz; i++)
if (mask >> i & 1)
nmask += (1 << one[i]);
ans += sub[nmask] * ((sz - __builtin_popcount(mask)) % 2 == 0 ? 1 : -1);
}
}
printf("%d\n", ans);
}
return 0;
}
Compilation message
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 340 KB | Output is correct |
| 2 | Correct | 1 ms | 340 KB | Output is correct |
| 3 | Correct | 1 ms | 340 KB | Output is correct |
| 4 | Correct | 1 ms | 340 KB | Output is correct |
| 5 | Correct | 2 ms | 340 KB | Output is correct |
| 6 | Correct | 1 ms | 340 KB | Output is correct |
| 7 | Correct | 1 ms | 340 KB | Output is correct |
| 8 | Correct | 1 ms | 340 KB | Output is correct |
| 9 | Correct | 1 ms | 340 KB | Output is correct |
| 10 | Correct | 1 ms | 340 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 340 KB | Output is correct |
| 2 | Correct | 1 ms | 340 KB | Output is correct |
| 3 | Correct | 1 ms | 340 KB | Output is correct |
| 4 | Correct | 1 ms | 340 KB | Output is correct |
| 5 | Correct | 2 ms | 340 KB | Output is correct |
| 6 | Correct | 1 ms | 340 KB | Output is correct |
| 7 | Correct | 1 ms | 340 KB | Output is correct |
| 8 | Correct | 1 ms | 340 KB | Output is correct |
| 9 | Correct | 1 ms | 340 KB | Output is correct |
| 10 | Correct | 1 ms | 340 KB | Output is correct |
| 11 | Correct | 758 ms | 4312 KB | Output is correct |
| 12 | Correct | 698 ms | 3972 KB | Output is correct |
| 13 | Correct | 607 ms | 3248 KB | Output is correct |
| 14 | Correct | 608 ms | 3324 KB | Output is correct |
| 15 | Correct | 1113 ms | 4452 KB | Output is correct |
| 16 | Correct | 713 ms | 3492 KB | Output is correct |
| 17 | Correct | 713 ms | 3552 KB | Output is correct |
| 18 | Correct | 342 ms | 5332 KB | Output is correct |
| 19 | Correct | 513 ms | 2352 KB | Output is correct |
| 20 | Correct | 782 ms | 3912 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 340 KB | Output is correct |
| 2 | Correct | 1 ms | 340 KB | Output is correct |
| 3 | Correct | 1 ms | 340 KB | Output is correct |
| 4 | Correct | 1 ms | 340 KB | Output is correct |
| 5 | Correct | 2 ms | 340 KB | Output is correct |
| 6 | Correct | 1 ms | 340 KB | Output is correct |
| 7 | Correct | 1 ms | 340 KB | Output is correct |
| 8 | Correct | 1 ms | 340 KB | Output is correct |
| 9 | Correct | 1 ms | 340 KB | Output is correct |
| 10 | Correct | 1 ms | 340 KB | Output is correct |
| 11 | Correct | 758 ms | 4312 KB | Output is correct |
| 12 | Correct | 698 ms | 3972 KB | Output is correct |
| 13 | Correct | 607 ms | 3248 KB | Output is correct |
| 14 | Correct | 608 ms | 3324 KB | Output is correct |
| 15 | Correct | 1113 ms | 4452 KB | Output is correct |
| 16 | Correct | 713 ms | 3492 KB | Output is correct |
| 17 | Correct | 713 ms | 3552 KB | Output is correct |
| 18 | Correct | 342 ms | 5332 KB | Output is correct |
| 19 | Correct | 513 ms | 2352 KB | Output is correct |
| 20 | Correct | 782 ms | 3912 KB | Output is correct |
| 21 | Correct | 605 ms | 4428 KB | Output is correct |
| 22 | Correct | 963 ms | 4648 KB | Output is correct |
| 23 | Correct | 825 ms | 3700 KB | Output is correct |
| 24 | Correct | 747 ms | 3416 KB | Output is correct |
| 25 | Correct | 637 ms | 5288 KB | Output is correct |
| 26 | Correct | 915 ms | 3904 KB | Output is correct |
| 27 | Correct | 888 ms | 3988 KB | Output is correct |
| 28 | Correct | 360 ms | 6348 KB | Output is correct |
| 29 | Correct | 555 ms | 2380 KB | Output is correct |
| 30 | Correct | 813 ms | 4496 KB | Output is correct |
| 31 | Correct | 1231 ms | 4536 KB | Output is correct |
| 32 | Correct | 899 ms | 4360 KB | Output is correct |
| 33 | Correct | 636 ms | 3380 KB | Output is correct |
| 34 | Correct | 769 ms | 3360 KB | Output is correct |
| 35 | Correct | 914 ms | 3860 KB | Output is correct |
| 36 | Correct | 338 ms | 2380 KB | Output is correct |
| 37 | Correct | 1105 ms | 4368 KB | Output is correct |
| 38 | Correct | 583 ms | 2368 KB | Output is correct |
| 39 | Correct | 806 ms | 3580 KB | Output is correct |
| 40 | Correct | 770 ms | 3404 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 340 KB | Output is correct |
| 2 | Correct | 1 ms | 340 KB | Output is correct |
| 3 | Correct | 1 ms | 340 KB | Output is correct |
| 4 | Correct | 1 ms | 340 KB | Output is correct |
| 5 | Correct | 2 ms | 340 KB | Output is correct |
| 6 | Correct | 1 ms | 340 KB | Output is correct |
| 7 | Correct | 1 ms | 340 KB | Output is correct |
| 8 | Correct | 1 ms | 340 KB | Output is correct |
| 9 | Correct | 1 ms | 340 KB | Output is correct |
| 10 | Correct | 1 ms | 340 KB | Output is correct |
| 11 | Correct | 90 ms | 9680 KB | Output is correct |
| 12 | Correct | 90 ms | 9804 KB | Output is correct |
| 13 | Correct | 113 ms | 9664 KB | Output is correct |
| 14 | Correct | 146 ms | 9664 KB | Output is correct |
| 15 | Correct | 101 ms | 9820 KB | Output is correct |
| 16 | Correct | 122 ms | 9692 KB | Output is correct |
| 17 | Correct | 123 ms | 9676 KB | Output is correct |
| 18 | Correct | 70 ms | 9944 KB | Output is correct |
| 19 | Correct | 86 ms | 9544 KB | Output is correct |
| 20 | Correct | 100 ms | 9788 KB | Output is correct |
| 21 | Correct | 108 ms | 9732 KB | Output is correct |
| 22 | Correct | 122 ms | 9676 KB | Output is correct |
| 23 | Correct | 96 ms | 9680 KB | Output is correct |
| 24 | Correct | 125 ms | 9660 KB | Output is correct |
| 25 | Correct | 126 ms | 9664 KB | Output is correct |
| 26 | Correct | 68 ms | 9532 KB | Output is correct |
| 27 | Correct | 93 ms | 9792 KB | Output is correct |
| 28 | Correct | 84 ms | 9548 KB | Output is correct |
| 29 | Correct | 104 ms | 9676 KB | Output is correct |
| 30 | Correct | 127 ms | 9672 KB | Output is correct |
| 31 | Correct | 91 ms | 9680 KB | Output is correct |
| 32 | Correct | 135 ms | 9932 KB | Output is correct |
| 33 | Correct | 123 ms | 9788 KB | Output is correct |
| 34 | Correct | 70 ms | 9548 KB | Output is correct |
| 35 | Correct | 111 ms | 9696 KB | Output is correct |
| 36 | Correct | 109 ms | 9668 KB | Output is correct |
| 37 | Correct | 109 ms | 9692 KB | Output is correct |
| 38 | Correct | 116 ms | 9684 KB | Output is correct |
| 39 | Correct | 114 ms | 9660 KB | Output is correct |
| 40 | Correct | 110 ms | 9720 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 340 KB | Output is correct |
| 2 | Correct | 1 ms | 340 KB | Output is correct |
| 3 | Correct | 1 ms | 340 KB | Output is correct |
| 4 | Correct | 1 ms | 340 KB | Output is correct |
| 5 | Correct | 2 ms | 340 KB | Output is correct |
| 6 | Correct | 1 ms | 340 KB | Output is correct |
| 7 | Correct | 1 ms | 340 KB | Output is correct |
| 8 | Correct | 1 ms | 340 KB | Output is correct |
| 9 | Correct | 1 ms | 340 KB | Output is correct |
| 10 | Correct | 1 ms | 340 KB | Output is correct |
| 11 | Correct | 758 ms | 4312 KB | Output is correct |
| 12 | Correct | 698 ms | 3972 KB | Output is correct |
| 13 | Correct | 607 ms | 3248 KB | Output is correct |
| 14 | Correct | 608 ms | 3324 KB | Output is correct |
| 15 | Correct | 1113 ms | 4452 KB | Output is correct |
| 16 | Correct | 713 ms | 3492 KB | Output is correct |
| 17 | Correct | 713 ms | 3552 KB | Output is correct |
| 18 | Correct | 342 ms | 5332 KB | Output is correct |
| 19 | Correct | 513 ms | 2352 KB | Output is correct |
| 20 | Correct | 782 ms | 3912 KB | Output is correct |
| 21 | Correct | 605 ms | 4428 KB | Output is correct |
| 22 | Correct | 963 ms | 4648 KB | Output is correct |
| 23 | Correct | 825 ms | 3700 KB | Output is correct |
| 24 | Correct | 747 ms | 3416 KB | Output is correct |
| 25 | Correct | 637 ms | 5288 KB | Output is correct |
| 26 | Correct | 915 ms | 3904 KB | Output is correct |
| 27 | Correct | 888 ms | 3988 KB | Output is correct |
| 28 | Correct | 360 ms | 6348 KB | Output is correct |
| 29 | Correct | 555 ms | 2380 KB | Output is correct |
| 30 | Correct | 813 ms | 4496 KB | Output is correct |
| 31 | Correct | 1231 ms | 4536 KB | Output is correct |
| 32 | Correct | 899 ms | 4360 KB | Output is correct |
| 33 | Correct | 636 ms | 3380 KB | Output is correct |
| 34 | Correct | 769 ms | 3360 KB | Output is correct |
| 35 | Correct | 914 ms | 3860 KB | Output is correct |
| 36 | Correct | 338 ms | 2380 KB | Output is correct |
| 37 | Correct | 1105 ms | 4368 KB | Output is correct |
| 38 | Correct | 583 ms | 2368 KB | Output is correct |
| 39 | Correct | 806 ms | 3580 KB | Output is correct |
| 40 | Correct | 770 ms | 3404 KB | Output is correct |
| 41 | Correct | 90 ms | 9680 KB | Output is correct |
| 42 | Correct | 90 ms | 9804 KB | Output is correct |
| 43 | Correct | 113 ms | 9664 KB | Output is correct |
| 44 | Correct | 146 ms | 9664 KB | Output is correct |
| 45 | Correct | 101 ms | 9820 KB | Output is correct |
| 46 | Correct | 122 ms | 9692 KB | Output is correct |
| 47 | Correct | 123 ms | 9676 KB | Output is correct |
| 48 | Correct | 70 ms | 9944 KB | Output is correct |
| 49 | Correct | 86 ms | 9544 KB | Output is correct |
| 50 | Correct | 100 ms | 9788 KB | Output is correct |
| 51 | Correct | 108 ms | 9732 KB | Output is correct |
| 52 | Correct | 122 ms | 9676 KB | Output is correct |
| 53 | Correct | 96 ms | 9680 KB | Output is correct |
| 54 | Correct | 125 ms | 9660 KB | Output is correct |
| 55 | Correct | 126 ms | 9664 KB | Output is correct |
| 56 | Correct | 68 ms | 9532 KB | Output is correct |
| 57 | Correct | 93 ms | 9792 KB | Output is correct |
| 58 | Correct | 84 ms | 9548 KB | Output is correct |
| 59 | Correct | 104 ms | 9676 KB | Output is correct |
| 60 | Correct | 127 ms | 9672 KB | Output is correct |
| 61 | Correct | 91 ms | 9680 KB | Output is correct |
| 62 | Correct | 135 ms | 9932 KB | Output is correct |
| 63 | Correct | 123 ms | 9788 KB | Output is correct |
| 64 | Correct | 70 ms | 9548 KB | Output is correct |
| 65 | Correct | 111 ms | 9696 KB | Output is correct |
| 66 | Correct | 109 ms | 9668 KB | Output is correct |
| 67 | Correct | 109 ms | 9692 KB | Output is correct |
| 68 | Correct | 116 ms | 9684 KB | Output is correct |
| 69 | Correct | 114 ms | 9660 KB | Output is correct |
| 70 | Correct | 110 ms | 9720 KB | Output is correct |
| 71 | Correct | 910 ms | 14556 KB | Output is correct |
| 72 | Correct | 974 ms | 14636 KB | Output is correct |
| 73 | Correct | 1259 ms | 13188 KB | Output is correct |
| 74 | Execution timed out | 2060 ms | 13492 KB | Time limit exceeded |
| 75 | Halted | 0 ms | 0 KB | - |