| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 548093 | 2022-04-12T11:33:33 Z | wmch13 | Snake Escaping (JOI18_snake_escaping) | C++14 | 2000 ms | 16140 KB |
#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<pair<ll,int>, null_type,less<pair<ll,int>>, rb_tree_tag,tree_order_statistics_node_update>
const int INF = 1e7;
const ll longINF = 1e17;
const int mxN = 1 << 20;
const int mxM = 1e5 + 9;
const int MOD = 998244353;
const double pi = acos (-1);
void setIO (string s) {
freopen ((s + ".in").c_str(), "r", stdin);
freopen ((s + ".out").c_str(), "w", stdout);
return;
}
int sub[mxN], sup[mxN], A[mxN];
bool oddParity (int x) {
return __builtin_popcount (x) % 2;
}
void solve () {
int L, Q;
cin >> L >> Q;
string s;
cin >> s;
for (int i = 0; i < (1 << L); i++)
sub[i] = sup[i] = A[i] = (s[i] - '0');
for (int i = 0; i < L; i++) {
for (int mask = 0; mask < (1 << L); mask++) {
if (mask & (1 << i)) {
sub[mask] += sub[mask ^ (1 << i)];
} else {
sup[mask] += sup[mask ^ (1 << i)];
}
}
}
while (Q--) {
int zero = 0, one = 0, any = 0;
for (int i = 0; i < L; i++) {
char c;
cin >> c;
zero <<= 1;
one <<= 1;
any <<= 1;
if (c == '0') {
zero++;
} else if (c == '1') {
one++;
} else any++;
}
int res = 0;
if (__builtin_popcount (any) <= 6) {
for (int mask = any; mask > 0; mask = (mask - 1) & any)
res += A[mask | one];
res += A[one];
} else if (__builtin_popcount (zero) <= 6) {
for (int mask = zero; mask > 0; mask = (mask - 1) & zero)
res += sup[mask | one] * (oddParity (mask) ? -1 : 1);
res += sup[one] * (oddParity (0) ? -1 : 1);
} else {
for (int mask = one; mask > 0; mask = (mask - 1) & one)
res += sub[mask | any] * (oddParity (mask ^ one) ? -1 : 1);
res += sub[any] * (oddParity (one) ? -1 : 1);
}
cout << res << "\n";
}
return;
}
int main () {
int t = 1;
//cin >> t;
//ios_base::sync_with_stdio (0);
//cin.tie (0);
//setIO ("deleg");
//preCalc ();
while (t--) {
//initialize common variables
//go solve
solve ();
}
return 0;
}
Compilation message
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 3 ms | 340 KB | Output is correct |
| 2 | Correct | 3 ms | 340 KB | Output is correct |
| 3 | Correct | 3 ms | 312 KB | Output is correct |
| 4 | Correct | 3 ms | 340 KB | Output is correct |
| 5 | Correct | 3 ms | 340 KB | Output is correct |
| 6 | Correct | 3 ms | 316 KB | Output is correct |
| 7 | Correct | 3 ms | 340 KB | Output is correct |
| 8 | Correct | 3 ms | 316 KB | Output is correct |
| 9 | Correct | 3 ms | 340 KB | Output is correct |
| 10 | Correct | 3 ms | 340 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 3 ms | 340 KB | Output is correct |
| 2 | Correct | 3 ms | 340 KB | Output is correct |
| 3 | Correct | 3 ms | 312 KB | Output is correct |
| 4 | Correct | 3 ms | 340 KB | Output is correct |
| 5 | Correct | 3 ms | 340 KB | Output is correct |
| 6 | Correct | 3 ms | 316 KB | Output is correct |
| 7 | Correct | 3 ms | 340 KB | Output is correct |
| 8 | Correct | 3 ms | 316 KB | Output is correct |
| 9 | Correct | 3 ms | 340 KB | Output is correct |
| 10 | Correct | 3 ms | 340 KB | Output is correct |
| 11 | Correct | 1951 ms | 14996 KB | Output is correct |
| 12 | Correct | 1941 ms | 14636 KB | Output is correct |
| 13 | Correct | 1947 ms | 13964 KB | Output is correct |
| 14 | Correct | 1920 ms | 14256 KB | Output is correct |
| 15 | Execution timed out | 2021 ms | 14732 KB | Time limit exceeded |
| 16 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 3 ms | 340 KB | Output is correct |
| 2 | Correct | 3 ms | 340 KB | Output is correct |
| 3 | Correct | 3 ms | 312 KB | Output is correct |
| 4 | Correct | 3 ms | 340 KB | Output is correct |
| 5 | Correct | 3 ms | 340 KB | Output is correct |
| 6 | Correct | 3 ms | 316 KB | Output is correct |
| 7 | Correct | 3 ms | 340 KB | Output is correct |
| 8 | Correct | 3 ms | 316 KB | Output is correct |
| 9 | Correct | 3 ms | 340 KB | Output is correct |
| 10 | Correct | 3 ms | 340 KB | Output is correct |
| 11 | Correct | 1951 ms | 14996 KB | Output is correct |
| 12 | Correct | 1941 ms | 14636 KB | Output is correct |
| 13 | Correct | 1947 ms | 13964 KB | Output is correct |
| 14 | Correct | 1920 ms | 14256 KB | Output is correct |
| 15 | Execution timed out | 2021 ms | 14732 KB | Time limit exceeded |
| 16 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 3 ms | 340 KB | Output is correct |
| 2 | Correct | 3 ms | 340 KB | Output is correct |
| 3 | Correct | 3 ms | 312 KB | Output is correct |
| 4 | Correct | 3 ms | 340 KB | Output is correct |
| 5 | Correct | 3 ms | 340 KB | Output is correct |
| 6 | Correct | 3 ms | 316 KB | Output is correct |
| 7 | Correct | 3 ms | 340 KB | Output is correct |
| 8 | Correct | 3 ms | 316 KB | Output is correct |
| 9 | Correct | 3 ms | 340 KB | Output is correct |
| 10 | Correct | 3 ms | 340 KB | Output is correct |
| 11 | Correct | 186 ms | 16080 KB | Output is correct |
| 12 | Correct | 184 ms | 16044 KB | Output is correct |
| 13 | Correct | 207 ms | 15924 KB | Output is correct |
| 14 | Correct | 239 ms | 15920 KB | Output is correct |
| 15 | Correct | 187 ms | 16084 KB | Output is correct |
| 16 | Correct | 223 ms | 15920 KB | Output is correct |
| 17 | Correct | 215 ms | 16064 KB | Output is correct |
| 18 | Correct | 190 ms | 16120 KB | Output is correct |
| 19 | Correct | 212 ms | 15808 KB | Output is correct |
| 20 | Correct | 171 ms | 16016 KB | Output is correct |
| 21 | Correct | 179 ms | 16048 KB | Output is correct |
| 22 | Correct | 217 ms | 15924 KB | Output is correct |
| 23 | Correct | 200 ms | 15956 KB | Output is correct |
| 24 | Correct | 211 ms | 15944 KB | Output is correct |
| 25 | Correct | 237 ms | 15916 KB | Output is correct |
| 26 | Correct | 184 ms | 15956 KB | Output is correct |
| 27 | Correct | 208 ms | 16056 KB | Output is correct |
| 28 | Correct | 211 ms | 15912 KB | Output is correct |
| 29 | Correct | 209 ms | 15992 KB | Output is correct |
| 30 | Correct | 246 ms | 16012 KB | Output is correct |
| 31 | Correct | 198 ms | 15968 KB | Output is correct |
| 32 | Correct | 247 ms | 16008 KB | Output is correct |
| 33 | Correct | 255 ms | 15916 KB | Output is correct |
| 34 | Correct | 194 ms | 15852 KB | Output is correct |
| 35 | Correct | 219 ms | 16008 KB | Output is correct |
| 36 | Correct | 226 ms | 15992 KB | Output is correct |
| 37 | Correct | 208 ms | 15984 KB | Output is correct |
| 38 | Correct | 210 ms | 16032 KB | Output is correct |
| 39 | Correct | 220 ms | 15960 KB | Output is correct |
| 40 | Correct | 210 ms | 16140 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 3 ms | 340 KB | Output is correct |
| 2 | Correct | 3 ms | 340 KB | Output is correct |
| 3 | Correct | 3 ms | 312 KB | Output is correct |
| 4 | Correct | 3 ms | 340 KB | Output is correct |
| 5 | Correct | 3 ms | 340 KB | Output is correct |
| 6 | Correct | 3 ms | 316 KB | Output is correct |
| 7 | Correct | 3 ms | 340 KB | Output is correct |
| 8 | Correct | 3 ms | 316 KB | Output is correct |
| 9 | Correct | 3 ms | 340 KB | Output is correct |
| 10 | Correct | 3 ms | 340 KB | Output is correct |
| 11 | Correct | 1951 ms | 14996 KB | Output is correct |
| 12 | Correct | 1941 ms | 14636 KB | Output is correct |
| 13 | Correct | 1947 ms | 13964 KB | Output is correct |
| 14 | Correct | 1920 ms | 14256 KB | Output is correct |
| 15 | Execution timed out | 2021 ms | 14732 KB | Time limit exceeded |
| 16 | Halted | 0 ms | 0 KB | - |