Submission #1001191

#TimeUsernameProblemLanguageResultExecution timeMemory
1001191mispertionSnake Escaping (JOI18_snake_escaping)C++17
22 / 100
528 ms27884 KiB
#include<bits/stdc++.h> using namespace std; #pragma GCC optimize("unroll-loops") #pragma GCC optimize("O3") mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); typedef long long ll; typedef unsigned long long ull; typedef long double ld; typedef pair<ll, ll> pii; typedef pair<ll, ll> pll; #define pb push_back #define all(x) x.begin(), x.end() #define sz(x) (int)x.size() #define mispertion ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) #define F first #define S second #define getlast(s) (*s.rbegin()) #define debg cout << "OK\n" const ld PI = 3.1415926535; const int N = 1e6+10; const int M = 7e6 + 1; int mod = 1e9+7; const int infi = INT_MAX; const ll infl = LLONG_MAX; const int P = 2; int mult(int a, int b) { return a * 1LL * b % mod; } int sum(int a, int b) { if (a + b < 0) return a + b + mod; if (a + b >= mod) return a + b - mod; return a + b; } ll binpow(ll a, ll n) { if (n == 0) return 1; if (n % 2 == 1) { return binpow(a, n - 1) * a % mod; } else { ll b = binpow(a, n / 2); return b * b % mod; } } int n, q, a[N], sos[N], sou[N]; void solve(){ cin >> n >> q; string tmp; cin >> tmp; for(int i = 0; i < (1 << n); i++) sos[i] = sou[i] = a[i] = tmp[i] - '0'; //sum over subsets for(int i = 0; i < n; i++) for(int mask = 0; mask < (1 << n); mask++) if(mask & (1 << i)) sos[mask] += sos[mask ^ (1 << i)]; for(int i = 0; i < n; i++) for(int mask = (1 << n) - 1; mask >= 0; mask--) if(!(mask & (1 << i))) sou[mask] += sou[mask ^ (1 << i)]; while(q--){ vector<int> und = {}, zer = {}, one = {}; string s; cin >> s; reverse(all(s)); int mainm = 0, unmask = 0, zermask = 0; for(int i = 0; i < sz(s); i++){ if(s[i] == '?') und.pb(i), unmask += (1 << i); if(s[i] == '0') zer.pb(i), zermask += (1 << i); if(s[i] == '1') one.pb(i), mainm += (1 << i); } if(sz(und) <= sz(zer) && sz(und) <= sz(one)){ int ans = a[mainm]; for(int mask = unmask; mask > 0; mask = (mask - 1) & unmask){ ans += a[mask + mainm]; } cout << ans << '\n'; }else if(sz(zer) <= sz(und) && sz(one) >= sz(zer)){ int ans = sou[mainm]; for(int mask = zermask; mask > 0; mask = (mask - 1) & zermask){ int cnt = __builtin_popcount(mask); if(cnt % 2) ans -= sou[mask + mainm]; else ans += sou[mask + mainm]; } cout << ans << '\n'; }else{ int ans = 0; if(sz(one) % 2) ans -= sos[unmask]; else ans += sos[unmask]; for(int mask = mainm; mask > 0; mask = (mask - 1) & mainm){ int cnt = sz(one) - __builtin_popcount(mask); if(cnt % 2) ans -= sos[mask + unmask]; else ans += sos[mask + unmask]; } cout << ans << '\n'; } } } signed main() { mispertion; int t = 1; //cin >> t; while(t--){ solve(); } return 0; }
#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...