# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
64539 | 2018-08-04T20:15:16 Z | keko37 | Snake Escaping (JOI18_snake_escaping) | C++14 | 9 ms | 500 KB |
#include<iostream> using namespace std; const int MAXN = 21; int n, q; char l[MAXN]; int val[1<<MAXN], sum0[1<<MAXN], sum1[1<<MAXN]; void precompute () { for (int i=0; i<(1<<n); i++) { sum0[i] = val[i]; sum1[i] = val[i ^ ((1<<n) - 1)]; } for (int i=0; i<n; i++) { for (int j=0; j<(1<<n); j++) { if (j & (1<<i)) sum0[j] += sum0[j ^ (1<<i)]; if (j & (1<<i)) sum1[j] += sum1[j ^ (1<<i)]; } } } void ispis (int x) { for (int i=n-1; i>=0; i--) { cout << (bool) (x & (1<<i)); } cout << endl; } int main () { cin >> n >> q; for (int i=0; i<(1<<n); i++) { char c; cin >> c; val[i] = c - '0'; } precompute(); for (int tc=0; tc<q; tc++) { int a = 0, b = 0, c = 0; for (int i=0; i<n; i++) { cin >> l[i]; if (l[i] == '?') { a ^= (1<<(n-1-i)); } else if (l[i] == '0') { b ^= (1<<(n-1-i)); } else { c ^= (1<<(n-1-i)); } } int sol = 0, mask = 0; if (__builtin_popcount(a) <= n/3) { do { sol += val[mask | c]; } while (mask = (mask-a) & a); } else if (__builtin_popcount(b) <= n/3) { do { if (__builtin_popcount(mask | a) & 1) { sol -= sum1[mask | a]; } else { sol += sum1[mask | a]; } } while (mask = (mask-b) & b); if (sol < 0) sol = -sol; } else { do { if (__builtin_popcount(mask | a) & 1) { sol -= sum1[mask | a]; } else { sol += sum1[mask | a]; } } while (mask = (mask-c) & c); if (sol < 0) sol = -sol; } printf("%d\n", sol); } return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 376 KB | Output is correct |
2 | Incorrect | 9 ms | 500 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 376 KB | Output is correct |
2 | Incorrect | 9 ms | 500 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 376 KB | Output is correct |
2 | Incorrect | 9 ms | 500 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 376 KB | Output is correct |
2 | Incorrect | 9 ms | 500 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 376 KB | Output is correct |
2 | Incorrect | 9 ms | 500 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |