Submission #522224

#	Time	Username	Problem	Language	Result	Execution time	Memory
522224		Monarchuwu	Snake Escaping (JOI18_snake_escaping)	C++17	22 / 100	381 ms	26200 KiB

snake_escaping

#include<iostream>
#include<algorithm>
#include<string>
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long ll;

const int N = 2e6 + 10;
int l, q;
string s;

int pw3[13 + 1], a[N];
void prep() {
    pw3[0] = 1;
    for (int i = 1; i <= l; ++i)
        pw3[i] = pw3[i - 1] * 3;

    for (int i = 0, msk; i < s.size(); ++i) {
        msk = 0;
        for (int j = 0; j < l; ++j)
            if (i >> j & 1) msk += pw3[j];
        a[msk] = s[i] ^ 48;
    }

    for (int j = 0; j < l; ++j)
        for (int msk = 0; msk < pw3[l]; ++msk)
            if (msk / pw3[j] % 3 == 2)
                a[msk] += a[msk - pw3[j]] + a[msk - pw3[j] * 2];
}

int main() {
    cin.tie(NULL)->sync_with_stdio(false);
    cin >> l >> q >> s;
    prep();

    while (q--) {
        string t; cin >> t;
        int msk(0);
        for (char c : t) {
            msk *= 3;
            if (c == '1') ++msk;
            else if (c == '?') msk += 2;
        }
        cout << a[msk] << '\n';
    }
}
/**  /\_/\
 *  (= ._.)
 *  / >0  \>1
**/

Compilation message (stderr)

snake_escaping.cpp: In function 'void prep()':
snake_escaping.cpp:18:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |     for (int i = 0, msk; i < s.size(); ++i) {
      |                          ~~^~~~~~~~~~

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