Submission #385901

#	Time	Username	Problem	Language	Result	Execution time	Memory
385901		ntabc05101	Snake Escaping (JOI18_snake_escaping)	C++14	100 / 100	1138 ms	47632 KiB

snake_escaping

#include<bits/stdc++.h>
using namespace std;

#define LL long long

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

        int L, Q; string S;
        cin >> L >> Q >> S;

        int M = 1 << L;
        int sup[M], sub[M], c[M];
        for (int i = 0; i < M; i++) {
                sup[i] = sub[i] = c[i] = S[i] - '0';
        }
        int n_bit[M];
        for (int i = 0; i < M; i++) {
                n_bit[i] = __builtin_popcount(i);
        }

        for (int i = 0; i < L; i++) {
                for (int j = 0; j < M; j++) {
                        if (j >> i & 1) {
                                sub[j] += sub[j ^ (1 << i)];
                        }
                        else {
                                sup[j] += sup[j ^ (1 << i)];
                        }
                }
        }

        while (Q--) {
                cin >> S; 
                reverse(begin(S), end(S));

                int A = 0, B = 0, C = 0;
                for (int i = 0; i < L; i++) {
                        if (S[i] == '0') {
                                A |= 1 << i;
                        }
                        else if (S[i] == '1') {
                                B |= 1 << i;
                        }
                        else {
                                C |= 1 << i;
                        }
                }

                int result = 0;
                if (n_bit[A] <= L / 3) {
                        result = sup[B];
                        for (int i = A; i > 0; i = (i - 1) & A) {
                                result += (1 - ((n_bit[i] & 1) << 1)) * sup[B | i];
                        }
                }
                else if (n_bit[B] <= L / 3) {
                        result = sub[M - 1 ^ A];
                        for (int i = B; i > 0; i = (i - 1) & B) {
                                result += (1 - ((n_bit[i] & 1) << 1)) * sub[M - 1 ^ (A | i)];
                        }
                }
                else if (n_bit[C] <= L / 3) {
                        result = c[B];
                        for (int i = C; i > 0; i = (i - 1) & C) {
                                result += c[B | i];
                        }
                }

                cout << result << "\n";
        }

        return 0;
}

Compilation message (stderr)

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:58:40: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   58 |                         result = sub[M - 1 ^ A];
      |                                      ~~^~~
snake_escaping.cpp:60:79: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   60 |                                 result += (1 - ((n_bit[i] & 1) << 1)) * sub[M - 1 ^ (A | i)];
      |                                                                             ~~^~~

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