Submission #522223

#	Time	Username	Problem	Language	Result	Execution time	Memory
522223		Monarchuwu	Snake Escaping (JOI18_snake_escaping)	C++17	12 / 100	228 ms	16488 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], a[N];
void prep() {
    pw3[0] = 1;
    for (int i = 1; i < 13; ++i)
        pw3[i] = pw3[i - 1] * 3;

    for (int i = 0, msk, x; i < s.size(); ++i) {
        msk = 0, x = i;
        for (int j = 0; j < l; ++j)
            if (x >> 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:31: 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, x; i < s.size(); ++i) {
      |                             ~~^~~~~~~~~~

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