This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// Judges with GCC >= 12 only needs Ofast
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("O3,no-stack-protector,fast-math,unroll-loops,tree-vectorize")
// MLE optimization
// #pragma GCC optimize("conserve-stack")
// Old judges
// #pragma GCC target("sse4.2,popcnt,lzcnt,abm,mmx,fma,bmi,bmi2")
// New judges. Test with assert(__builtin_cpu_supports("avx2"));
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")
// Atcoder
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma")
#include <bits/stdc++.h>
using namespace std;
// #define int ll
#define MAX LLONG_MAX
#define st first
#define nd second
#define endl '\n'
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(), x.end()
typedef long long ll;
typedef pair< int, int > ii;
typedef pair< int, ii > iii;
typedef vector< int > vi;
typedef vector< ii > vii;
typedef vector< iii > viii;
typedef vector< vi > vvi;
typedef vector< vii > vvii;
typedef vector< viii > vviii;
struct Trie{
struct Node{
int cnt, exist, sum;
Node* child[2];
Node(){
cnt = exist = sum = 0;
child[0] = child[1] = NULL;
}
};
Node* root;
Trie(){
root = new Node();
}
int LG;
void init(int n){
LG = n-1;
}
void add(int n, int val){
Node* p = root;
for(int i=LG; i>=0; i--){
bool c = n & (1<<i);
if(p->child[c] == NULL) p->child[c] = new Node();
p = p->child[c];
p->cnt++;
}
p->exist++;
p->sum += val;
}
int dequy(Node* p, string& s, int i){
if(i == LG + 1) return p->sum;
if(s[i] == '0') return dequy(p->child[0], s, i+1);
else if(s[i] == '1') return dequy(p->child[1], s, i+1);
else return dequy(p->child[0], s, i+1) + dequy(p->child[1], s, i+1);
}
int find(string s){
return dequy(root, s, 0);
}
} trie;
map<string, int> m;
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, q; cin >> n >> q;
string s; cin >> s;
trie.init(n);
for(int i=0; i<(1<<n); i++) trie.add(i, s[i] - '0');
while(q--){
string tmp; cin >> tmp;
if(m[tmp] != 0) cout << m[tmp] << endl;
else{
int ans = trie.find(tmp);
m[tmp] = ans;
cout << ans << endl;
}
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |