Submission #445836

#	Time	Username	Problem	Language	Result	Execution time	Memory
445836		JovanB	Snake Escaping (JOI18_snake_escaping)	C++17	100 / 100	1993 ms	43288 KiB

snake_escaping

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

using ll = long long;
using ld = long double;

const int N = 20;
int str[1<<N];
int sub[1<<N];
int over[1<<N];

int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout.precision(10);
    cout << fixed;

    int n, qrs;
    cin >> n >> qrs;
    string td;
    cin >> td;
    for(int i=0; i<(1<<n); i++){
        str[i] = td[i] - '0';
        sub[i] = over[i] = str[i];
    }
    for(int i=0; i<n; i++){
        for(int mask=0; mask<(1<<n); mask++){
            if(mask & (1 << i)) sub[mask] += sub[mask ^ (1 << i)];
        }
    }
    for(int i=0; i<n; i++){
        for(int mask=0; mask<(1<<n); mask++){
            if(!(mask & (1 << i))) over[mask] += over[mask ^ (1 << i)];
        }
    }
    while(qrs--){
        string s;
        cin >> s;
        reverse(s.begin(), s.end());
        int cp = 0, c1 = 0, c0 = 0;
        for(auto c : s){
            if(c == '?') cp++;
            else if(c == '0') c0++;
            else c1++;
        }
        int mn = min(min(c0, c1), cp);
        if(cp == mn){
            vector <int> pos;
            int p = 0;
            int res = 0;
            for(int i=0; i<n; i++){
                char c = s[i];
                if(c == '?') pos.push_back(1 << i);
                else if(c == '1') p += (1 << i);
            }
            if(cp == 0){
                cout << str[p] << "\n";
                continue;
            }
            for(int mask=0; mask<(1<<pos.size()); mask++){
                int g = p;
                for(int j=0; j<pos.size(); j++) if((1 << j) & mask) g += pos[j];
                res += str[g];
            }
            cout << res << "\n";
        }
        else if(c0 == mn){
            vector <int> pos;
            int p = 0;
            for(int i=0; i<n; i++){
                char c = s[i];
                if(c == '0') pos.push_back(1 << i);
                else if(c == '1') p += (1 << i);
            }
            if(c0 == 0){
                cout << over[p] << "\n";
                continue;
            }
            int res = 0;
            for(int mask=0; mask<(1<<pos.size()); mask++){
                int g = p, pr = 1;
                for(int j=0; j<pos.size(); j++){
                    if((1 << j) & mask){
                        g += pos[j];
                        pr = -pr;
                    }
                }
                res += pr*over[g];
            }
            cout << res << "\n";
        }
        else{
            vector <int> pos;
            int p = 0;
            for(int i=0; i<n; i++){
                char c = s[i];
                if(c == '1') pos.push_back(1 << i);
                else if(c == '?') p += (1 << i);
            }
            if(c1 == 0){
                cout << sub[p] << "\n";
                continue;
            }
            int res = 0;
            for(int mask=0; mask<(1<<pos.size()); mask++){
                int g = p, pr = 1;
                for(int j=0; j<pos.size(); j++){
                    if(!((1 << j) & mask)){
                        pr = -pr;
                    }
                    else g += pos[j];
                }
                res += pr*sub[g];
            }
            cout << res << "\n";
        }
    }
    return 0;
}

Compilation message (stderr)

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:61:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |                 for(int j=0; j<pos.size(); j++) if((1 << j) & mask) g += pos[j];
      |                              ~^~~~~~~~~~~
snake_escaping.cpp:81:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |                 for(int j=0; j<pos.size(); j++){
      |                              ~^~~~~~~~~~~
snake_escaping.cpp:106:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |                 for(int j=0; j<pos.size(); j++){
      |                              ~^~~~~~~~~~~

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