Submission #329342

#TimeUsernameProblemLanguageResultExecution timeMemory
329342HoneyBadgerSnake Escaping (JOI18_snake_escaping)C++17
22 / 100
1105 ms65540 KiB
#include <iostream> #include <iomanip> #include <cstdio> #include <vector> #include <bitset> #include <string> #include <cstring> #include <map> #include <set> #include <stack> #include <queue> #include <deque> #include <utility> #include <algorithm> #include <random> #include <cmath> #include <cassert> #include <climits> #include <ctime> #include <chrono> #include <unordered_map> #pragma GCC optimize("Ofast") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx,avx2,tune=native") #ifdef LOCAL #define dbg(x) cout << #x << " : " << x << endl; #else #define dbg(x) #endif #define pb push_back #define ppb pop_back() #define mp make_pair #define fi(a, b) for (int i = a; i < b; i++) #define fj(a, b) for (int j = a; j < b; j++) #define fk(a, b) for (int k = a; k < b; k++) #define fi1(a, b) for (int i = a - 1; i >= b; i--) #define fj1(a, b) for (int j = a - 1; j >= b; j--) #define fk1(a, b) for (int k = a - 1; k >= b; k--) #define fx(x, a) for (auto& x : a) #define rep(i, a, b) for (int i = a; i < b; ++i) #define rep1(i, a, b) for (int i = a - 1; i >= b; --i) #define siz(x) (int)x.size() #define lb lower_bound #define ub upper_bound #define all(x) x.begin(), x.end() using namespace std; template<typename T1, typename T2>inline void mine(T1 &x, const T2 &y) { if (y < x) x = y; } template<typename T1, typename T2>inline void maxe(T1 &x, const T2 &y) { if (x < y) x = y; } ostream& operator << (ostream &out, const vector<int> &b) { for (auto k : b) out << k << ' '; return out; } typedef long long ll; typedef unsigned long long ull; typedef long double ld; typedef char ch; typedef string str; typedef pair<int, int> pii; typedef vector<int> vi; typedef vector<vi> vvi; typedef vector<pii> vpii; typedef vector<vpii> vvpii; typedef vector<ch> vch; typedef vector<vch> vvch; typedef vector<str> vs; const int MOD = 1000000007; const int INF = 1000000050; const long long BIG = (long long)2e18 + 50; const double EPS = 1e-9; const int BUBEN = 6; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int n, q; ll pw3[21]; char a[1 << 20]; map<ll, int> ht; void init() { pw3[0] = 1; fi(1, 21) pw3[i] = pw3[i - 1] * 3; } //pos3.size() <= BUBEN slow int gen(int mask, vi &pos3) { if (pos3.empty()) return a[mask]; int i = pos3.back(); pos3.ppb; int res = gen(mask + (1 << i), pos3) + gen(mask, pos3); pos3.pb(i); return res; } int get(ll mask3, int mask2, vi &pos3) { if (pos3.size() <= BUBEN) { return gen(mask2, pos3); } auto it = ht.find(mask3); if (it == ht.end()) { int i = pos3.back(); pos3.ppb; int res = get(mask3 - pw3[i], mask2 ^ (1 << i), pos3) + get(mask3 - 2 * pw3[i], mask2, pos3); pos3.pb(i); ht[mask3] = res; return res; } else { return it->second; } } int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); init(); cin >> n >> q; for (int i = 0; i < (1 << n); ++i) { char c; cin >> c; a[i] = c - '0'; } while (q--) { vi pos3; ll mask3 = 0; int mask2 = 0; fi(0, n) { char c; cin >> c; if (c == '1') { mask2 += 1 << (n - i - 1); mask3 += 1 * pw3[n - i - 1]; } else if (c == '?') { mask3 += 2 * pw3[n - i - 1]; pos3.pb(n - i - 1); } } cout << get(mask3, mask2, pos3) << '\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...