제출 #1228895

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1228895		Dedibeat	Snake Escaping (JOI18_snake_escaping)	C++20	100 / 100	1178 ms	26908 KiB

snake_escaping

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define F first 
#define S second 
#define all(x) (x).begin(), (x).end()
template<typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &p)
{
    return os << "(" << p.F << "," << p.S << ")";
}
template<typename T> 
void print(const T &v, int lim = 1e9)
{
    for(auto x : v)
        if(lim-- > 0) cout << x << " ";
    cout << "\n";
}


int main()
{
    ios::sync_with_stdio(0); cin.tie(NULL);
    int n, q;
    cin >> n >> q;
    string s, t;
    cin >> s;
    int F0[(1 << n)];
    int F1[(1 << n)];
    for(int mask = 0; mask < (1 << n); mask++)
    {
        F0[mask] = s[mask] - '0';
        F1[mask] = s[(1 << n) - mask - 1] - '0';
        
    }
    for(int i = 0; i < n; i++)
    {
        for(int mask = 0; mask < (1 << n); mask++)
        {
            if(mask & (1 << i)) 
            {
                F0[mask] += F0[mask ^ (1 << i)];
                F1[mask] += F1[mask ^ (1 << i)];
            }
        }
    }

    while(q--)
    {
        cin >> t;
        vector<int> e0, e1, e2;
        int num = 0, num2 = 0;
        for(int i = 0; i < t.size(); i++)
        {
            int exp = (1 << (t.size() - i - 1));

            if(t[i] == '0') e0.push_back(exp);
            else if(t[i] == '1') e1.push_back(exp), num2 += exp;
            else 
            {
                e2.push_back(exp);
                num += exp;
            }
        }

        // cout << "num: " << num << endl;

        if(e0.size() <= 6)
        {
            int m = e0.size(), ans = 0;
            // print(e0);
            for(int mask = 0; mask < (1 << m); mask++)
            {
                int tmp = 0;
                int p_cnt = 0;
                for(int i = 0; i < m; i++)
                {
                    if(mask & (1 << i)) 
                    {
                        tmp |= e0[i];
                        p_cnt++;
                    }
                }

                if(p_cnt & 1)
                    ans += F1[tmp | num];
                else 
                    ans -= F1[tmp | num];
            }

            cout << abs(ans) << '\n';
        }
        else if(e1.size() <= 6)
        {
            int m = e1.size(), ans = 0;
            // print(e0);
            for(int mask = 0; mask < (1 << m); mask++)
            {
                int tmp = 0;
                int p_cnt = 0;
                for(int i = 0; i < m; i++)
                {
                    if(mask & (1 << i)) 
                    {
                        tmp |= e1[i];
                        p_cnt++;
                    }
                }

                if(p_cnt & 1)
                    ans += F0[tmp | num];
                else 
                    ans -= F0[tmp | num];
            }

            cout << abs(ans) << '\n';

        }
        else 
        {
            int m = e2.size(), ans = 0;
            // print(e0);
            for(int mask = 0; mask < (1 << m); mask++)
            {
                int tmp = 0;
                for(int i = 0; i < m; i++)
                {
                    if(mask & (1 << i)) 
                        tmp |= e2[i];
                }
                ans += s[tmp | num2] - '0';
            }
            cout << ans << "\n";
        }

    }


}

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