제출 #1290655

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1290655		proplayer	Snake Escaping (JOI18_snake_escaping)	C++20	100 / 100	407 ms	25024 KiB

snake_escaping

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
const int maxN = (1 << 20) + 5;
const int Mod = 1e9 + 7;
int f[maxN], g[maxN];
int a[maxN], cntb[maxN];
int n, q;
void input()
{
    cin >> n >> q;
    for (int i = 0; i < (1 << n); ++i)
    {
        char c;
        cin >> c;
        a[i] = c - '0';
        cntb[i] = __builtin_popcountll(i);
        f[i] = a[i];
        g[i] = a[i];
    }

}
string s;
void solve()
{
    for (int i = 0; i < n; ++i)
        for (int mask = 0; mask < (1 << n); ++mask)
        {
            if (mask & (1 << i)) f[mask] += f[mask ^ (1 << i)];
            if (!(mask & (1 << i))) g[mask] += g[mask ^ (1 << i)];
        }
    for (int i = 1; i <= q; ++i)
    {
        cin >> s;
        int mask = 0, mask1 = 0, mask0 = 0;
        int cnt1 = 0, cnt0 = 0, cnt = 0;
        for (int j = 0; j < s.size(); ++j)
        {
            if (s[j] == '?')
            {
                mask |= (1 << (s.size() - j - 1));
                ++cnt;
            }
            if (s[j] == '0')
            {
                mask0 |= (1 << (s.size() - j - 1));
                ++cnt0;
            }
            if (s[j] == '1')
            {
                mask1 |= (1 << (s.size() - j - 1));
                ++cnt1;
            }
        }
        int res = 0;
        if (cnt == min({cnt, cnt0, cnt1}))
        {
            res = a[mask1];
            for (int s = mask; s > 0; s = (s - 1) & mask)
                res += a[mask1 ^ s];
        }
        else if (cnt1 == min({cnt, cnt0, cnt1}))
        {
            mask0 = ((1 << n) - 1) ^ mask0;
            res = f[mask0];
            //cerr << mask0 << " " << res << " " << f[9] << "a\n";
            for (int s = mask1; s > 0; s = (s - 1) & mask1)
            {
                if (cntb[s] % 2 == 1) res -= f[mask0 ^ s];
                else res += f[mask0 ^ s];
//                cerr << (mask0 ^ s) << "\n";
            }
        }
        else
        {
            res = g[mask1];
            for (int s = mask0; s > 0; s = (s - 1) & mask0)
            {
                if (cntb[s] % 2 == 1) res -= g[mask1 ^ s];
                else res += g[mask1 ^ s];
            }
        }
        cout << res << "\n";
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
//    freopen("P2.inp","r",stdin);
//    freopen("P2.out","w",stdout);
    input();
    solve();
}

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