Submission #1095157

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095157		LinhLewLew	Snake Escaping (JOI18_snake_escaping)	C++17	100 / 100	792 ms	39116 KiB

snake_escaping

// PhuThuyRuntime <3
// A secret makes a woman woman

#include <bits/stdc++.h>

using namespace std;

#define eb emplace_back
#define ef emplace_front
#define pb push_back
#define pf push_front
#define all(v) v.begin(), v.end()
#define ins insert
#define lb lower_bound
#define ub upper_bound
#define fo(i, l, r) for(int i = l; i <= r; i++)
#define foi(i, l, r) for(int i = l; i >= r; i--)
#define elif else if
#define el cout << "\n";
#define pii pair<int, int>
#define pli pair<ll, int>
#define pll pair<ll, ll>
#define pil pair<int, ll>
#define fi first
#define se second
#define in(x) freopen(x, "r", stdin)
#define out(x) freopen(x, "w", stdout)
#define ll long long
#define ull unsigned long long
#define pob pop_back
#define bs binary_search
#define vi vector<int>
#define vii vector<pair<int, int>>
#define getbit(i, j) ((i >> j) & 1)
#define offbit(i, j) ((1 << j) ^ i)
#define onbit(i, j) ((1 << j) | i)
const int N = 1e5 + 2;
const ll mod = 1e9 + 7;
const int inf = INT_MAX;
const int base = 31;
const long double EPS = 1e-9;
const long double pi = acos(-1.0);
int n, Q;
char a[1 << 20];
void inp(){
     cin >> n >> Q;
     fo(i, 0, (1 << n) - 1) cin >> a[i];
}
int fin[1 << 20], fout[1 << 20];
void sol(){
     fo(i, 0, (1 << n) - 1) fin[i] = fout[i] = a[i] - '0';
     fo(i, 0, n - 1){
          fo(mask, 0, (1 << n) - 1){
               if(getbit(mask, i)){
                    fin[mask] += fin[offbit(mask, i)];
               }
               else fout[mask] += fout[onbit(mask, i)];
          }
     }
     while(Q--){
          int va = 0, vb = 0, vc = 0;
          foi(i, n - 1, 0){
               char ch; cin >> ch;
               if(ch == '0') va |= 1 << i;
               else if(ch == '1') vb |= 1 << i;
               else vc |= 1 << i;
          }
          int cnta = __builtin_popcount(va);
          int cntb = __builtin_popcount(vb);
          int cntc = __builtin_popcount(vc);
          if(cntc <= 6){
               int ans = 0;
               for(int mask = vc; mask; mask = vc & (mask - 1)){
                    ans += a[mask | vb] - '0';
               }
               ans += a[vb] - '0';
               cout << ans, el
          }
          else if(cnta <= 6){
               int ans = 0;
               for(int mask = va; mask; mask = va & (mask - 1)){
                    int sign = __builtin_popcount(mask) & 1 ? -1 : 1;
                    ans += sign * fout[mask | vb];
               }
               ans += fout[vb];
               cout << ans, el
          }
          else if(cntb <= 6){
               int ans = 0;
               for(int mask = vb; mask; mask = vb & (mask - 1)){
                    int sign = (cntb - __builtin_popcount(mask)) & 1 ? -1 : 1;
                    ans += sign * fin[mask | vc];
               }
               if(cntb & 1) ans -= fin[vc];
               else ans += fin[vc];
               cout << ans, el
          }
     }
}
int main(){
     ios_base::sync_with_stdio(false);
     cin.tie(NULL);
     inp();
     sol();
     return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 10 / 10
• Subtask 4: 53 / 53
• Subtask 5: 25 / 25