oj.uz

Submission #956193

# Submission time Handle Problem Language Result Execution time Memory
956193 2024-04-01T09:38:31 Z samvar_0907 Snake Escaping (JOI18_snake_escaping) C++17
0 / 100
 4 ms 604 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -