Submission #285764

#	Time	Username	Problem	Language	Result	Execution time	Memory
285764		glikcakbn	Snake Escaping (JOI18_snake_escaping)	C++14	100 / 100	1886 ms	42488 KiB

snake_escaping

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int L, T; cin >> L >> T;
    int n = (1 << L);

    int A[n];
    for(int i = 0; i < n; ++i)
    {
        char c; cin >> c;
        A[i] = c - '0';
    }

    int B[n]; for(int i = 0; i < n; ++i) B[i] = A[i];
    for(int i = 0; i < L; ++i)
    {
        for(int j = 0; j < n; ++j)
            if(j >> i & 1) B[j] += B[j ^ (1 << i)];
    }

    int C[n]; for(int i = 0; i < n; ++i) C[i] = A[i];
    for(int i = 0; i < L; ++i)
    {
        for(int j = 0; j < n; ++j)
            if(j >> i & 1) C[j ^ (1 << i)] += C[j];
    }

//    for(auto i : A) cout << i << ' '; cout << endl;
//    for(auto i : B) cout << i << ' '; cout << endl;
//    for(auto i : C) cout << i << ' '; cout << endl;

    while(T--)
    {
        int a = 0, b = 0, c = 0;
        int arr[L];
        for(int i = L - 1; i >= 0; --i)
        {
            char t; cin >> t;
            if(t == '0') arr[i] = 0, ++c;
            else if(t == '1') arr[i] = 1, ++b;
            else arr[i] = 2, ++a;
        }

        if(a <= b && a <= c)
        {
            int N = 1 << a;
            vector<int> bt; int bs = 0;
            for(int i = 0; i < L; ++i)
            {
                if(arr[i] == 2) bt.push_back(1 << i);
                else if(arr[i] == 1) bs |= (1 << i);
            }

            int ans = A[bs];
            for(int i = 1; i < N; ++i)
            {
                int t = __builtin_ctz(i);
                for(int j = 0; j < t; ++j) bs ^= bt[j];
                bs ^= bt[t];
                ans += A[bs];
            }
            cout << ans << '\n';
        }

        else if(b <= a && b <= c)
        {
            int N = 1 << b;
            vector<int> bt; int bs = 0;
            for(int i = 0; i < L; ++i)
            {
                if(arr[i] == 1) bt.push_back(1 << i), bs |= (1 << i);
                else if(arr[i] == 2) bs |= (1 << i);
            }

            long long ans = B[bs];
            for(int i = 1; i < N; ++i)
            {
                int t = __builtin_ctz(i);
                for(int j = 0; j < t; ++j) bs ^= bt[j];
                bs ^= bt[t];
                if(__builtin_parity(i)) ans -= B[bs];
                else ans += B[bs];
            }
            cout << ans << '\n';
        }

        else
        {
            int N = 1 << c;
            vector<int> bt; int bs = 0;
            for(int i = 0; i < L; ++i)
            {
                if(arr[i] == 0) bt.push_back(1 << i);
                else if(arr[i] == 1) bs |= (1 << i);
            }

            long long ans = C[bs];
            for(int i = 1; i < N; ++i)
            {
                int t = __builtin_ctz(i);
                for(int j = 0; j < t; ++j) bs ^= bt[j];
                bs ^= bt[t];
                if(__builtin_parity(i)) ans -= C[bs];
                else ans += C[bs];
            }
            cout << ans << '\n';
        }
    }
}

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