Submission #1181070

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181070		jerzyk	Snake Escaping (JOI18_snake_escaping)	C++20	100 / 100	1048 ms	21936 KiB

snake_escaping

#include <bits/stdc++.h>

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000'000'000'000'000'000LL;
const int II = 2'000'000'000;
const ll M = 1000'000'007LL;
const int K = 20;
const int N = 1<<K;
int tab[N];
int s1[N], s2[N];

void LiczDP(int n, int k)
{
    for(int i = 0; i < n; ++i)
        s1[i] = s2[i] = tab[i];
    for(int j = 0; j < k; ++j)
        for(int i = 0; i < n; ++i)
            if(((1<<j)&i) == 0) s1[i ^ (1<<j)] += s1[i];
    for(int j = 0; j < k; ++j)
        for(int i = n - 1; i >= 0; --i)
            if((1<<j)&i) s2[i ^ (1<<j)] += s2[i];
}

int AnsQ(int k, int val, vector<int> p)
{
    int m = (int)p.size(), ans = 0;
    for(int i = 0; i < (1<<m); ++i)
    {
        int cur = 0;
        for(int j = 0; j < m; ++j)
            if((1<<j)&i)
                cur += (1<<p[j]);
        ans += tab[val | cur];
    }
    return ans;
}

int Ans0(int k, int val, vector<int> p)
{
    ll ans = 0LL;
    int m = (int)p.size();
    for(int i = 0; i < (1<<m); ++i)
    {
        int cur = val;
        for(int j = 0; j < m; ++j)
            if((1<<j)&i)
                cur ^= (1<<p[j]);
        if(__builtin_popcount(cur) % 2 == 0)
            ans += s2[cur];
        else
            ans -= s2[cur];
    }
    if(ans < 0) ans *= -1LL;
    return ans;
}

int Ans1(int k, int val, vector<int> p)
{
    ll ans = 0LL;
    int m = (int)p.size();
    for(int i = 0; i < (1<<m); ++i)
    {
        int cur = val;
        for(int j = 0; j < m; ++j)
            if((1<<j)&i)
                cur ^= (1<<p[j]);
        if(__builtin_popcount(cur) % 2 == 0)
            ans += s1[cur];
        else
            ans -= s1[cur];
    }
    if(ans < 0) ans *= -1LL;
    return ans;
}

void Solve()
{
    int k, q, n;
    string s;
    cin >> k >> q;
    cin >> s;
    n = (1<<k);
    for(int i = 0; i < n; ++i)
        tab[i] = (s[i] - '0');
    LiczDP(n, k);
    for(int i = 1; i <= q; ++i)
    {
        int val = 0;
        vector<int> p0, p1, pq;
        cin >> s;
        reverse(s.begin(), s.end());
        for(int j = 0; j < k; ++j)
        {
            if(s[j] == '?') pq.pb(j);
            if(s[j] == '0') p0.pb(j);
            if(s[j] == '1')
            {
                p1.pb(j);
                val += (1<<j);
            }
        }
        int ans = 0LL;
        if((int)pq.size() <= min((int)p1.size(), (int)p0.size()))
            ans = AnsQ(k, val, pq);
        else if((int)p0.size() <= (int)p1.size())
            ans = Ans0(k, val, p0);
        else
        {
            for(int j = 0; j < (int)pq.size(); ++j)
                val += (1<<pq[j]);
            ans = Ans1(k, val, p1);
        }
        cout << ans << "\n";
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    //int t; cin >> t;
    //while(t--)
        Solve();

    return 0;
}

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