Submission #1115155

#TimeUsernameProblemLanguageResultExecution timeMemory
1115155Dan4LifeSnake Escaping (JOI18_snake_escaping)C++17
22 / 100
1656 ms60404 KiB
#include <bits/stdc++.h> using namespace std; #define pb push_back #define sz(a) (int)a.size() #define all(a) begin(a),end(a) string s; int n, l, q; const int p3[] = {1,3,9,27,81,243,729,729*3,729*9,729*27,729*81,729*243,729*729}; const int B1 = 6; const int B2 = 20-B1; const int N = p3[B1]; int score[N+2][(1<<B2)+2], tot[N+2]; int calc(string lol){ int p = 1, ans = 0, xd; for(int i = 0; i < B1; i++){ if(lol[i]=='?') xd=2; else xd = lol[i]-'0'; ans+=xd*p, p*=3; } return ans; } int calc(int lol){ int p = 1, ans = 0; while(lol){ int r = lol%2; lol/=2; ans+=r*p; p*=3; } return ans; } int32_t main(){ ios_base::sync_with_stdio(false); cin.tie(0); cin >> l >> q >> s; n = (1<<l); if(l<B1){ for(int _ = 0; _ < q; _++){ string t; cin >> t; reverse(all(t)); int cnt = 0; for(int i = 0; i < n; i++){ int ok = 1; for(int j = 0; j < l; j++) ok&=(t[j]=='?' or (t[j]-'0')==(i>>j&1)); cnt+=ok*(s[i]-'0'); } cout << cnt << "\n"; } return 0; } l-=B1; for(int mask = 0; mask < n; mask++){ int mask1 = calc(mask&((1<<B1)-1)); int mask2 = mask>>B1; int sc = s[mask]-'0'; tot[mask1]+=sc; score[mask1][mask2]+=sc; } for(int mask = 0; mask < (1<<(B1*2)); mask++){ string t = "", t2 = ""; for(int i = 0; i < B1*2; i+=2){ int cur = mask>>i&1; t+=(char)(cur+'0'); if(mask>>(i+1)&1) cur=2; t2+=(char)(cur+'0'); } int mask1 = calc(t); int mask2 = calc(t2); if(t==t2) continue; tot[mask2]+=tot[mask1]; for(int i = 0; i < (1<<l); i++) score[mask2][i]+=score[mask1][i]; } for(int _ = 0; _ < q; _++){ string t; cin >> t; reverse(all(t)); int x = calc(t.substr(0,B1)); t = t.substr(B1); int cnt = 0, ans = 0, xd2 = 0; vector<int> pos, pos2; pos.clear(); pos2.clear(); for(int i = 0; i < sz(t); i++){ if(t[i]=='?') pos.pb(i),cnt++; else{ pos2.pb(i); if(t[i]=='1') xd2+=1<<i; } } if(cnt*2<=B2){ for(int mask = 0; mask < (1<<cnt); mask++){ int xd = 0; for(int i = 0; i < cnt; i++) if(mask>>i&1) xd+=1<<pos[i]; ans+=score[x][xd+xd2]; } } else{ cnt = sz(pos2); ans = tot[x]; for(int mask = 1; mask < (1<<cnt); mask++){ int num = __builtin_popcount(mask), xd=0; for(int i = 0; i < cnt; i++) if(mask>>i&1) xd+=(1<<pos2[i])*(t[pos2[i]]=='0'); ans+=(num%2?-1:1)*score[x][xd]; } } 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...