Submission #333121

#TimeUsernameProblemLanguageResultExecution timeMemory
333121soroushSnake Escaping (JOI18_snake_escaping)C++14
0 / 100
2 ms492 KiB
/* #pragma GCC optimize("O2") #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #pragma GCC target("avx,avx2,sse,sse2,fma") //*/ #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair<int ,int > pii; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const ll maxn = 2e6+100; const ll mod =1e9+7; const ld PI = acos((ld)-1); #define pb push_back #define endl '\n' #define dokme(x) cout << x , exit(0) #define migmig ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) #define ms(x , y) memset(x , y , sizeof x) ll pw(ll a, ll b, ll md = mod){ll res = 1;while(b){if(b&1){res=(a*res)%md;}a=(a*a)%md;b>>=1;}return(res);} int l , q; int a[maxn]; string s; int ans[maxn]; int p[30]; void sub1(){ for(int i = 0 ; i < p[l] ; i ++){ int res = 0; int x = i; for(int j = l ; j >= 0 ; j --){ if(x >= 2*p[j]){ x = i; x-=2*p[j]; ans[i] = ans[x] + ans[x + p[j]]; break; } if(x >= p[j]) res += (1 << j); x%=p[j]; if(j == 0)ans[i] = a[res]; } } while(q -- ){ string t; cin >> t; reverse(t.begin() , t.end()); int x = 0; for(int i = 0 ; i < l ; i ++) if(t[i] == '?')x+=p[i]*2; else if(t[i] == '1')x+=p[i]; cout << ans[x] << endl; } exit(0); } vector < string > t; int res[maxn]; int32_t main(){ migmig; cin >> l >> q; cin >> s; for(int i = 0 ; i < (1 << l) ; i ++) a[i] = s[i] - '0'; p[0] = 1; for(int i = 1 ; i < 16; i ++) p[i] = p[i - 1] * 3; if(l <= 9) sub1(); t.reserve(q + 1); for(int i = 1 ; i <= q ; i ++) cin >> t[i] , reverse(t[i].begin() , t[i].end()); for(int k = 0 ; k < 128 ; k ++){ for(int i = 0 ; i < p[l] ; i ++){ int res = 0; int x = i; for(int j = l ; j >= 0 ; j --){ if(x >= 2*p[j]){ x = i; x-=2*p[j]; ans[i] = ans[x] + ans[x + p[j]]; break; } if(x >= p[j]) res += (1 << j); x%=p[j]; if(j == 0)ans[i] = a[res * 128 + k]; } } for(int i = 1 ; i <= q ; i ++){ bool ok = 1; for(int j = 0 ; j < 7 ; j ++){ if(k&(1 << j)){if(t[i][j] == '0'){ok=0 ;break;}} else if(t[i][j] == '1'){ok=0 ;break;} } if(!ok)continue; int x = 0; for(int j = 7 ; j < l ; j ++) if(t[i][j] == '?')x+=p[i]*2; else if(t[i][j] == '1')x+=p[i]; res[i] += ans[x]; } } for(int i = 1; i <= q ; i ++) cout << res[i] << endl; return(0); }
#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...