oj.uz

Submission #445837

# Submission time Handle Problem Language Result Execution time Memory
445837 2021-07-19T20:26:14 Z JovanB Snake Escaping (JOI18_snake_escaping) C++17
0 / 100
 1 ms 332 KB 
#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;
                int k = mask;
                while(k){
                    int x = k & -k;
                    int v = __builtin_ctz(x);
                    g += pos[v];
                    k -= x;
                }
                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;
                int k = mask;
                while(k){
                    int x = k & -k;
                    int v = __builtin_ctz(x);
                    pr -= pr;
                    g += pos[v];
                    k -= x;
                }
                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 != '0') p += (1 << i);
                if(c == '1') pos.push_back(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;
                int k = mask;
                while(k){
                    int x = k & -k;
                    int v = __builtin_ctz(x);
                    pr -= pr;
                    g -= pos[v];
                    k -= x;
                }
                res += pr*sub[g];
            }
            cout << res << "\n";
        }
    }
    return 0;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 7.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 53.0

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

Subtask #5
0 / 25.0

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