Submission #956193

#	Time	Username	Problem	Language	Result	Execution time	Memory
956193		samvar_0907	Snake Escaping (JOI18_snake_escaping)	C++17	0 / 100	4 ms	604 KiB

snake_escaping

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

map<string, int> dp;

int solve(const string &s) {
    if (dp.find(s) != dp.end())
        return dp[s];
    int count = 0;
    bool question_mark_found = false;
    for (char x : s) {
        if (x == '?') {
            question_mark_found = true;
            break;
        }
    }
    if (!question_mark_found) {
        for (char c : s) {
            count = count * 2 + (c - '0');
        }
        return count;
    }
    for (int i = 0; i < s.length(); ++i) {
        if (s[i] == '?') {
            string s0 = s;
            s0[i] = '0';
            count += solve(s0);
            string s1 = s;
            s1[i] = '1';
            count += solve(s1);
            break;
        }
    }
    return dp[s] = count;
}

int main() {
    int l, q;
    cin >> l >> q;
    for (int i = 0; i < (1 << l); i++) {
        char a;
        cin >> a;
        a = a - '0';
        string binaryString = bitset<20>(i).to_string();
        dp[binaryString] = a;
    }
    for (int i = 1; i <= q; i++) {
        string s;
        cin >> s;
        for (int x = 0; x < 20 - l; x++){
            s.insert(s.begin(), '0');
        }
        cout << solve(s);
    }
}

Compilation message (stderr)

snake_escaping.cpp: In function 'int solve(const string&)':
snake_escaping.cpp:23:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     for (int i = 0; i < s.length(); ++i) {
      |                     ~~^~~~~~~~~~~~

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