제출 #1283321

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1283321		dat	Snake Escaping (JOI18_snake_escaping)	C++20	22 / 100	1184 ms	14276 KiB

snake_escaping

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int Nmax = 20, LIM = 1 << Nmax;

int n, q;
int a[LIM], f[LIM], f0[LIM];
string s;

void enter(){
    cin >> n >> q >> s;
    int lim = 1 << n;
    for(int i = 0; i < lim; i++){
        a[i] = f[i] = f0[i] = s[i] - '0';
    }

    for(int i = 0; i < n; i++){
        for(int mask = 0; mask < lim; mask++){
            if(mask >> i & 1) f[mask] += f[mask ^ (1 << i)];
            else f0[mask] += f0[mask ^ (1 << i)];
        }
    }


    for(int i = 0; i < q; i++){
        cin >> s;
        int one = 0, zero = 0, ques = 0;
        reverse(s.begin(), s.end());
        for(int j = 0; j < n; j++){
            int bit = 1 << j;
            if(s[j] == '?') ques |= bit;
            else if(s[j] == '1') one |= bit;
            else zero |= bit;
        }

        int ans = 0;
        if(__builtin_popcount(ques) <= 6){
            for(int sub = ques;; sub = (sub - 1) & ques){
                ans += a[sub | one];
                if(sub == 0) break;
            }
        }
        else if(__builtin_popcount(one) <= 6){
            for(int sub = one;; sub = (sub - 1) & one){
                int diff = __builtin_popcount(one) - __builtin_popcount(sub);
                if(diff & 1) ans -= f[sub | ques];
                else ans += f[sub | ques];

                if(sub == 0) break;
            }
        }
        else if(__builtin_popcount(zero) <= 6){
            for(int sub = zero;; sub = (sub - 1) & zero){
                int diff = __builtin_popcount(sub);
                if(diff & 1) ans -= f0[sub | ques];
                else ans += f0[sub | ques];

                if(sub == 0) break;
            }
        }
        cout << ans << '\n';
    }


}
int main(){
    //freopen("SNAKE.INP", "r", stdin);
    enter();




}

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