Submission #1099128

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099128		Phuoc	Snake Escaping (JOI18_snake_escaping)	C++14	12 / 100	465 ms	65536 KiB

snake_escaping

#include <bits/stdc++.h>

using namespace std;

#define el '\n';
#define ll long long
#define fi first
#define se second
#define BIT(mask, i) (((mask) >> (i)) & 1)
#define MASK(i) (1LL << (i))

template <class T1, class T2>
    bool minimize(T1 &a, T2 b) {
        if(a > b) {a = b; return true;} return false;
    }

template <class T1, class T2>
    bool maximize(T1 &a, T2 b) {
        if(a < b) {a = b; return true;} return false;
    }

const int MOD = (int)1e9 + 7;

template <class T1, class T2> 
    void add (T1 &a, T2 b) {
        a += b;
        if (a >= MOD) a -= MOD;
    }

const int N = 50100;
const int oo = (int)1e9 + 7;
const ll INF = (ll)1e18 + 9LL;
const int LOG = 22;

int nSeg, nQuery;
string toxicity;

void init (void) {
    cin >> nSeg >> nQuery >> toxicity;
}

namespace subtask1 {
    bool ok (void) {
        return nSeg <= 10 && nQuery <= 1000;
    }

    long long res = 0;

    void Try (string s, int i, int mask) {
        if(i >= s.size()) {
            res += (toxicity[mask] - '0');
            return;
        }
        long long res = 0;
        if(s[i] != '?') {
            Try (s, i + 1, mask + (s[i] - '0') * MASK(i));
        }
        else {
            Try (s, i + 1, mask + MASK(i));
            Try (s, i + 1, mask);
        }
    }

    void solve (void) {
        for (int i = 1; i <= nQuery; i++) {
            string s; cin >> s;
            reverse(s.begin(), s.end());
            Try (s, 0, 0);
            cout << res << el;
            res = 0;
        }
    }
}

namespace subtask2 {
    bool ok (void) {
        return nSeg <= 13;
    }

    vector <string> pattern;

    void gen_pattern (int i, string s) {
        if(i >= nSeg) {
            pattern.push_back(s);
            return;
        }
        gen_pattern (i + 1, s + '0');
        gen_pattern (i + 1, s + '1');
        gen_pattern (i + 1, s + '?');
    }

    long long res = 0;

    void Try (string s, int i, int mask) {
        if(i >= s.size()) {
            res += (toxicity[mask] - '0');
            return;
        }
        if(s[i] != '?') {
            Try (s, i + 1, mask + (s[i] - '0') * MASK(i));
        }
        else {
            Try (s, i + 1, mask + MASK(i));
            Try (s, i + 1, mask);
        }
    }

    map <string, long long> ans;

    void solve (void) {
        gen_pattern(0, "");
        for (int i = 0; i < pattern.size(); i++) {
            Try (pattern[i], 0, 0);
            ans[pattern[i]] = res;
            // cout << pattern[i] << ' << el;
            res = 0;
        }

        for (int i = 1; i <= nQuery; i++) {
            string s; cin >> s;
            reverse(s.begin(), s.end());
            cout << ans[s] << el;
        }
    }
}

void solve (void) { 
    if(subtask1::ok()) {subtask1::solve(); return;}
    if(subtask2::ok()) {subtask2::solve(); return;}
}

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

    int ntest = 1; 

    while(ntest--) {
        init();
        solve();
    }
    return 0;
}

Compilation message (stderr)

snake_escaping.cpp: In function 'void subtask1::Try(std::string, int, int)':
snake_escaping.cpp:50:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |         if(i >= s.size()) {
      |            ~~^~~~~~~~~~~
snake_escaping.cpp:54:19: warning: unused variable 'res' [-Wunused-variable]
   54 |         long long res = 0;
      |                   ^~~
snake_escaping.cpp: In function 'void subtask2::Try(std::string, int, int)':
snake_escaping.cpp:95:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |         if(i >= s.size()) {
      |            ~~^~~~~~~~~~~
snake_escaping.cpp: In function 'void subtask2::solve()':
snake_escaping.cpp:112:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |         for (int i = 0; i < pattern.size(); i++) {
      |                         ~~^~~~~~~~~~~~~~~~

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