# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
42369 | 2018-02-26T14:30:31 Z | RezwanArefin01 | Snake Escaping (JOI18_snake_escaping) | C++14 | 2000 ms | 12836 KB |
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> ii; ll dp[1 << 20]; string b; int main(int argc, char const *argv[]) { int l, q; scanf("%d %d", &l, &q); cin >> b; for(int i = 0; i < (1 << l); i++) { dp[i] = b[i] - '0'; } for(int i = 0; i < l; i++) { for(int j = 0; j < (1 << l); j++) { if(j >> i & 1) dp[j] += dp[j ^ (1 << i)]; } } while(q--) { string s; cin >> s; int n0 = 0, n1 = 0, nw0t = 0; for(char c : s) { n0 += c == '0'; n1 += c == '1'; nw0t += c == '?'; } if(n1 == 0) { int num = 0; for(char c : s) num = (num << 1) + (c == '?'); cout << dp[num] << endl; } else if(nw0t == 0) { int num = 0; for(char c : s) num = (num << 1) + (c == '1'); cout << b[num] << endl; } else { vector<int> id; int basic = 0; for(int i = 0; i < s.size(); i++) { if(s[i] == '1') id.push_back(s.size() - 1 - i); if(s[i] == '?') s[i] = '1'; basic = (basic << 1) + (s[i] == '1'); } ll ans = 0; for(int mask = 0; mask < (1 << id.size()); mask++) { int cnt = __builtin_popcount(mask); int num = basic; for(int i = 0; i < id.size(); i++) { if(mask >> i & 1) num -= (1 << id[i]); } if(cnt & 1) ans -= dp[num]; else ans += dp[num]; //cout << bitset<4>(num).to_string() << endl; } cout << ans << endl; } } }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 248 KB | Output is correct |
2 | Correct | 3 ms | 364 KB | Output is correct |
3 | Correct | 4 ms | 448 KB | Output is correct |
4 | Correct | 4 ms | 532 KB | Output is correct |
5 | Correct | 4 ms | 688 KB | Output is correct |
6 | Correct | 4 ms | 688 KB | Output is correct |
7 | Correct | 4 ms | 688 KB | Output is correct |
8 | Correct | 3 ms | 708 KB | Output is correct |
9 | Correct | 3 ms | 708 KB | Output is correct |
10 | Correct | 6 ms | 724 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 248 KB | Output is correct |
2 | Correct | 3 ms | 364 KB | Output is correct |
3 | Correct | 4 ms | 448 KB | Output is correct |
4 | Correct | 4 ms | 532 KB | Output is correct |
5 | Correct | 4 ms | 688 KB | Output is correct |
6 | Correct | 4 ms | 688 KB | Output is correct |
7 | Correct | 4 ms | 688 KB | Output is correct |
8 | Correct | 3 ms | 708 KB | Output is correct |
9 | Correct | 3 ms | 708 KB | Output is correct |
10 | Correct | 6 ms | 724 KB | Output is correct |
11 | Execution timed out | 2033 ms | 6120 KB | Time limit exceeded |
12 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 248 KB | Output is correct |
2 | Correct | 3 ms | 364 KB | Output is correct |
3 | Correct | 4 ms | 448 KB | Output is correct |
4 | Correct | 4 ms | 532 KB | Output is correct |
5 | Correct | 4 ms | 688 KB | Output is correct |
6 | Correct | 4 ms | 688 KB | Output is correct |
7 | Correct | 4 ms | 688 KB | Output is correct |
8 | Correct | 3 ms | 708 KB | Output is correct |
9 | Correct | 3 ms | 708 KB | Output is correct |
10 | Correct | 6 ms | 724 KB | Output is correct |
11 | Execution timed out | 2033 ms | 6120 KB | Time limit exceeded |
12 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 248 KB | Output is correct |
2 | Correct | 3 ms | 364 KB | Output is correct |
3 | Correct | 4 ms | 448 KB | Output is correct |
4 | Correct | 4 ms | 532 KB | Output is correct |
5 | Correct | 4 ms | 688 KB | Output is correct |
6 | Correct | 4 ms | 688 KB | Output is correct |
7 | Correct | 4 ms | 688 KB | Output is correct |
8 | Correct | 3 ms | 708 KB | Output is correct |
9 | Correct | 3 ms | 708 KB | Output is correct |
10 | Correct | 6 ms | 724 KB | Output is correct |
11 | Execution timed out | 2044 ms | 12836 KB | Time limit exceeded |
12 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 248 KB | Output is correct |
2 | Correct | 3 ms | 364 KB | Output is correct |
3 | Correct | 4 ms | 448 KB | Output is correct |
4 | Correct | 4 ms | 532 KB | Output is correct |
5 | Correct | 4 ms | 688 KB | Output is correct |
6 | Correct | 4 ms | 688 KB | Output is correct |
7 | Correct | 4 ms | 688 KB | Output is correct |
8 | Correct | 3 ms | 708 KB | Output is correct |
9 | Correct | 3 ms | 708 KB | Output is correct |
10 | Correct | 6 ms | 724 KB | Output is correct |
11 | Execution timed out | 2033 ms | 6120 KB | Time limit exceeded |
12 | Halted | 0 ms | 0 KB | - |