Submission #763105

#TimeUsernameProblemLanguageResultExecution timeMemory
763105senthetaSnake Escaping (JOI18_snake_escaping)C++17
22 / 100
390 ms20200 KiB
// author : sentheta aka vanwij #ifdef VANWIJ #include"/home/user/code/bits/stdc++.h" #else #include"bits/stdc++.h" #endif using namespace std; #define Int long long #define V vector #define pii pair<int,int> #define ff first #define ss second static mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); #define pow2(x) (1LL<<(x)) #define msb(x) (63-__builtin_clzll(x)) #define bitcnt(x) (__builtin_popcountll(x)) #define nl '\n' #define _ << ' ' << #define all(x) (x).begin(), (x).end() #define rep(i,a,b) for(int i = (int)(a); i < (int)(b); i++) #define dbg(x) if(1) cout << "?" << #x << " : " << (x) << endl << flush; #define int long long // const Int MOD = 1e9+7; const Int MOD = 998244353; Int bpow(Int a,Int b){ Int ret = 1; for(;b; a=a*a%MOD,b/=2) if(b&1) ret = ret*a%MOD; return ret; } Int inv(Int a){return bpow(a,MOD-2);} void solve(); int TC, ALLTC; signed main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cout << fixed << setprecision(7); // cin >> ALLTC; for(TC=1; TC<=ALLTC; TC++) solve(); return 0; solve(); } const int N = 1<<18; int lg, n, q; string s; int sub[N], super[N]; void solve1(){ string t; cin >> t; reverse(all(t)); // dbg(t); int a=0, b=0, c=0; rep(i,0,lg){ if(t[i]=='0') a |= 1<<i; if(t[i]=='1') b |= 1<<i; if(t[i]=='?') c |= 1<<i; } // dbg(a); dbg(b); dbg(c); int ans = 0; if(bitcnt(a) <= 6){ for(int z=a; ; z=(z-1)&a){ int amt = super[b|z]; if(bitcnt(z)&1) amt *= -1; ans += amt; if(z==0) break; } } else if(bitcnt(b) <= 6){ for(int z=b; ; z=(z-1)&b){ int amt = sub[c|z]; if(bitcnt(z^b)&1) amt *= -1; ans += amt; if(z==0) break; } } else if(bitcnt(c) <= 6){ for(int z=c; ; z=(z-1)&c){ ans += s[b|z]-'0'; if(z==0) break; } } cout << ans << nl; } void solve(){ cin >> lg >> q >> s; n = 1<<lg; rep(i,0,n){ sub[i] = super[i] = s[i]-'0'; } rep(b,0,lg) rep(msk,0,n){ // include submask if(msk&1<<b){ sub[msk] += sub[msk^1<<b]; } // include supermask else{ super[msk] += super[msk^1<<b]; } } while(q--){ solve1(); } }
#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...