제출 #386144

#제출 시각아이디문제언어결과실행 시간메모리
386144CSQ31Snake Escaping (JOI18_snake_escaping)C++14
75 / 100
2031 ms23412 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 main() { //O(l * 2^l + q) owo int l,q; cin>>l>>q; vector<int>sub(1<<(l+1)),sup(1<<(l+1)); string snek; for(int i=0;i<(1<<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<(1<<l);j++){ if(j&(1<<i))sub[j]+=sub[j^(1<<i)]; else sup[j]+=sup[j^(1<<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); if(s[i] == '0')a.pb(l-i-1); if(s[i] == '1')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+=(1<<(l-i-1)); for(int i=0;i<(1<<sz(c));i++){ ll ncur = cur; for(int j=0;j<sz(c);j++){ if(i&(1<<j))ncur+=(1<<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+=(1<<(l-i-1)); for(int i=0;i<(1<<sz(a));i++){ ll ncur = cur; int cnt = 0; for(int j=0;j<sz(a);j++){ if(i&(1<<j)){ncur+=(1<<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+=(1<<(l-i-1)); for(int mask=0;mask<(1<<sz(b));mask++){ ll ncur = cur; int cnt = 0; for(int j=0;j<sz(b);j++){ if(mask&(1<<j)){ncur+=(1<<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...