Submission #386152

#TimeUsernameProblemLanguageResultExecution timeMemory
386152CSQ31Snake Escaping (JOI18_snake_escaping)C++14
75 / 100
2069 ms25216 KiB
#pragma GCC optimize("Ofast") #include<bits/stdc++.h> using namespace std; #define pb push_back #define fi first #define se second #define sz(a) (int)(a.size()) #define all(a) a.begin(),a.end() #define lb lower_bound #define ub upper_bound #define owo ios_base::sync_with_stdio(0);cin.tie(0); #define MOD (ll)(1e9+7) #define INF (ll)(1e18) #define debug(...) fprintf(stderr, __VA_ARGS__),fflush(stderr) #define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false);\ debug("%s time : %.4fs\n", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC)) typedef long long int ll; typedef long double ld; typedef pair<ll,ll> PII; typedef pair<int,int> pii; typedef vector<vector<int>> vii; typedef vector<vector<ll>> VII; typedef pair<int,pii> P; ll gcd(ll a,ll b){if(!b)return a;else return gcd(b,a%b);} int pw[22]; int main() { owo pw[0] = 1; for(int i=1;i<=21;i++)pw[i] = pw[i-1]*2; int l,q; cin>>l>>q; vector<int>sub(pw[(l+1)]),sup(pw[(l+1)]); string snek; for(int i=0;i<pw[l];i++){ char c;cin>>c; sub[i]+=c-'0'; sup[i]+=c-'0'; snek+=c; } for(int i=0;i<l;i++){ for(int j=0;j<pw[l];j++){ if(j&pw[i])sub[j]+=sub[j^pw[i]]; else sup[j]+=sup[j^pw[i]]; } } while(q--){ vector<int>a,b,c; string s;cin>>s; ll ans = 0; for(int i=0;i<l;i++){ if(s[i] == '?')c.pb(l-i-1); else if(s[i] == '0')a.pb(l-i-1); else b.pb(l-i-1); } int mn = min({sz(a),sz(b),sz(c)}); if(sz(c) == mn){ ll cur = 0; for(int i=0;i<l;i++)if(s[i]=='1')cur+=pw[(l-i-1)]; for(int i=0;i<pw[sz(c)];i++){ ll ncur = cur; for(int j=0;j<sz(c);j++){ if(i&pw[j])ncur+=pw[c[j]]; } ans+=snek[ncur]-'0'; } } else if(sz(a) == mn){ ll cur = 0; for(int i=0;i<l;i++)if(s[i] == '1')cur+=pw[(l-i-1)]; for(int i=0;i<pw[sz(a)];i++){ ll ncur = cur; int cnt = 0; for(int j=0;j<sz(a);j++){ if(i&pw[j]){ncur+=pw[a[j]];cnt++;} } if(cnt&1)ans-=sup[ncur]; else ans+=sup[ncur]; } }else{ ll cur = 0; for(int i=0;i<l;i++)if(s[i] == '?')cur+=pw[(l-i-1)]; for(int mask=0;mask<pw[sz(b)];mask++){ ll ncur = cur; int cnt = 0; for(int j=0;j<sz(b);j++){ if(mask&pw[j]){ncur+=pw[b[j]];} else cnt++; } if(cnt&1)ans-=sub[ncur]; else ans+=sub[ncur]; } } cout<<ans<<'\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...