Submission #893052

#TimeUsernameProblemLanguageResultExecution timeMemory
893052goodspeed0208Snake Escaping (JOI18_snake_escaping)C++14
22 / 100
280 ms32460 KiB
#include<iostream> #include<vector> #include<algorithm> #include<set> #include<map> #include<queue> #include<utility> #define int long long #define INF 1000000000000000000 #define pii pair<long long, long long> using namespace std; signed main() { ios::sync_with_stdio(false); cin.tie(0); int n, q, pn; cin >> n >> q; string s, c; cin >> s; vector<int>t(25); t[0] = 1; for (int i = 1 ; i < 25 ; i++) t[i] = t[i-1] * 3; pn = t[n]; vector<int>dp(pn+5, -1); int k = 0; for (int i = 0 ; i < pn ; i++) { for (int j = 0 ; j < n ; j++) { int tmp = i / t[j] % 3; if (tmp == 2) { dp[i] = dp[i-t[j]] + dp[i-t[j]*2]; break; } } //cout << dp[i] << " "; if (dp[i] == -1) { dp[i] = s[k] - '0'; k++; } //cout << dp[i] << "\n"; } while (q--) { cin >> c; int ask = 0; for (int i = 0 ; i < n ; i++) { if (c[i] == '1') ask += 1 * t[n-i-1]; else if (c[i] == '?') ask += 2 * t[n-i-1]; } cout << dp[ask] << "\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...