제출 #42164

#제출 시각아이디문제언어결과실행 시간메모리
42164festSnake Escaping (JOI18_snake_escaping)C++14
0 / 100
2033 ms584 KiB
// fest #include <bits/stdc++.h> #define pb push_back #define F first #define S second #define y1 dasdasfasfas #define x1 wqdadfasfasfas #define All(c) c.begin(), c.end() #define SZ(A) (int((A).size())) #define umap unordered_map #define FILENAME "" #define __ fflush(stdout) typedef long long ll; typedef long double ld; using namespace std; void FREOPEN() { #ifdef COMP freopen(".in", "r", stdin); freopen("1.out", "w", stdout); #else freopen(FILENAME".in", "r", stdin); freopen(FILENAME".out", "w", stdout); #endif } inline double Time() {return (clock() * 1.0) / CLOCKS_PER_SEC; } const int N = 20, inf = 1e9 * 2, MOD = (int)1e9 + 7; char CH[N]; const ll INF = 1e18; const int dx[] = {1, -1, 0, 0, -1, 1, -1, 1}; const int dy[] = {0, 0, 1, -1, -1, 1, 1, -1}; int ones[N], dp[2][2][1 << N], cost[2][1 << N], qs[N]; bool built[1 << N]; int n; inline int rev(int x) { int ret = 0; for (int i = 0; i < n; i++) { if (x & (1 << i)) continue; ret |= (1 << i); } return ret; } void build(int ty) { for (int mask = 0; mask < (1 << n); mask++) { dp[ty][0][mask] += cost[ty][mask]; if (mask & 1) dp[ty][0][mask] += cost[ty][mask ^ 1]; } for (int bit = 1; bit < n; bit++) { int j = (bit & 1); for (int mask = 0; mask < (1 << n); mask++) { dp[ty][j][mask] = dp[ty][j ^ 1][mask]; if (mask & (1 << bit)) dp[ty][j][mask] += dp[ty][j ^ 1][mask ^ (1 << bit)]; } } } inline int calc(int ty) { int ret = 0; int alw = 0; int mask = 0; for (int i = 0; i < n; i++) { if (qs[i] == 2) alw |= (1 << i); if (qs[i] == 1) mask |= (1 << i); } for (int pod = mask; ; pod = (pod - 1) & mask) { if (built[pod]) ret -= dp[ty][(n - 1) & 1][alw | pod]; else ret += dp[ty][(n - 1) & 1][alw | pod]; } return abs(ret); } int main() { int q; cin >> n >> q; scanf("\n"); for (int i = 0; i < (1 << n); i++) { char x = getchar(); cost[0][i] = (int)(x - '0'); cost[1][rev(i)] = (int)(x - '0'); } for (int mask = 0; mask < (1 << n); mask++) built[mask] = (__builtin_popcount(mask) & 1); build(0); build(1); while (q--) { getchar(); int zer = 0, one = 0, que = 0; for (int i = n - 1; i >= 0; i--) { char x = getchar(); if (x == '?') qs[i] = 2, que++; if (x == '1') qs[i] = 1, one++; if (x == '0') qs[i] = 0, zer++; } if (!one) { int ret = 0; for (int i = 0; i < n; i++) { if (qs[i] == 2) ret |= (1 << i); } printf("%d\n", dp[0][(n - 1) & 1][ret]); continue; } if (!zer) { int ret = 0; for (int i = 0; i < n; i++) { if (qs[i] == 2) ret |= (1 << i); } printf("%d\n", dp[1][(n - 1) & 1][ret]); continue; } if (que < 7) { int ans = 0; int mask = 0; int alw = 0; for (int i = 0; i < n; i++) { if (qs[i] == 2) mask |= (1 << i); if (qs[i] == 1) alw |= (1 << i); } for (int pod = mask; ; pod = (pod - 1) & mask) { ans += cost[0][alw | pod]; if (!pod) break; } printf("%d\n", ans); continue; } if (one < 7) { printf("%d\n", calc(0)); continue; } for (int i = 0; i < n; i++) if (qs[i] < 2) qs[i] ^= 1; printf("%d\n", calc(1)); } return 0; }

컴파일 시 표준 에러 (stderr) 메시지

snake_escaping.cpp: In function 'void FREOPEN()':
snake_escaping.cpp:25:37: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen(FILENAME".in", "r", stdin);
                                     ^
snake_escaping.cpp:26:39: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen(FILENAME".out", "w", stdout);
                                       ^
snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:89:13: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("\n");
             ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...