Submission #386149

#TimeUsernameProblemLanguageResultExecution timeMemory
386149CSQ31Snake Escaping (JOI18_snake_escaping)C++14
22 / 100
883 ms35236 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);} ll pw[22] = {1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048572,2097152}; int main() { owo ll l,q; cin>>l>>q; vector<ll>sub(pw[l+1]),sup(pw[l+1]); string snek; for(ll i=0;i<pw[l];i++){ char c;cin>>c; sub[i]+=c-'0'; sup[i]+=c-'0'; snek+=c; } for(ll i=0;i<l;i++){ for(ll 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<ll>a,b,c; string s;cin>>s; ll ans = 0; for(ll 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); } ll mn = min({sz(a),sz(b),sz(c)}); if(sz(c) == mn){ ll cur = 0; for(ll i=0;i<l;i++)if(s[i]=='1')cur+=(pw[l-i-1]); for(ll i=0;i<pw[sz(c)];i++){ ll ncur = cur; for(ll 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(ll i=0;i<l;i++)if(s[i] == '1')cur+=(pw[l-i-1]); for(ll i=0;i<pw[sz(a)];i++){ ll ncur = cur; ll cnt = 0; for(ll 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(ll i=0;i<l;i++)if(s[i] == '?')cur+=(pw[l-i-1]); for(ll mask=0;mask<pw[sz(b)];mask++){ ll ncur = cur; ll cnt = 0; for(ll 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...